14501: 퇴사

• toc {:toc}

문제 확인하기

풀이

처음 들었던 생각은 BFS/DFS를 사용해서 풀이하는 것이었는데 계속 잘 안 풀려서 다른 방식이 있는지를 계속해서 생각해봤다. DP 문제라는 것을 알긴 하는데 어떻게 풀어야할지 모르겠는 느낌이었다.

그러던 중 i일 이후 얻을 수 있는 돈은 i일 이후로 저장해 놓은 이후 해당 일에 도착했을 때 합치면 되겠다는 생각을 했다. 해당 일에 얻을 수 있는 최댓값을 계속해서 갱신하여 마지막 날에 얻을 수 있는 최댓값을 산출한다.

#include <bits/stdc++.h>
using namespace std;
#define X first
 
int N, T[20], P[20], res = 0;
int price[20] = {0,};
 
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int res = 0;
 
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> T[i] >> P[i];
    }
 
    for(int i=0; i<=N; i++){
        price[i] = max(price[i], res);
        if(P[i]+price[i] > price[i+T[i]] && i+T[i]< N+1)
            price[i+T[i]] = P[i] + price[i];
        if(res < price[i]) res = price[i];
    }
 
    cout << res << '\n';
 
    return 0;    
}