백준 14501 퇴사(brute force)

#include <iostream>
#include <algorithm>
using namespace std;
 
const int MAX = 15;
pair<int, int> priceofDay[MAX];
int num;
 
int maxProfit(int day)
{
    if (day == num)
        return 0;
    if (day > num)
        return -987654321;
    int sum = 0;
    sum += max(priceofDay[day].second + maxProfit(day + priceofDay[day].first), maxProfit(day + 1));
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> num;
    for (int i = 0; i < num; i++)
    {
        cin >> priceofDay[i].first >> priceofDay[i].second; //first가 day, second가 price
    }
    cout << maxProfit(0);
}

점화식을 세우는게 중요했던 문제였다. 

max(day의 일을 하는 경우, day에 일을 하지 않고 다음 날에 일을 하는 경우) 를 통해 풀 수 있었다. 

처음에 기저사례 설정을 if(day>=num) return 0; 로 했다. 이렇게 하니 day가 num-1인 경우가 자동으로 더해져 버렸다. 

따라서, 저렇게 기저사례를 두 개로 나누어서 설정하였다.

오랜만에 알고리즘 문제를 풀다보니 자잘한 실수들을 많이 하는 것 같다. 무엇을 하든 꾸준히 하는 것이 제일 중요할 것 같다.