15486번

15486번 - 퇴사(2)

기존의 퇴사 문제와 같다. 하지만 N제한이 커졌기 때문에 기존 문제처럼 완전탐색으로 해결할 수 없다. 

(시간복잡도가 최대 N^2 이 되기 때문에)

그리고 int 형 변수를 사용할지 long long 을 사용할지 확인해보면  P의 최대값이 1000이고, N의 1500000 이므로, 최대값은 15억으로 int 형 

변수로 충분히 해결할 수 있다.

최종적으로 DP를 이용해서 문제를 해결할 수 있다.

<정답 코드>

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 1500001
int N;
int P[MAX];
int T[MAX];
int D[MAX];
int go(int k)
{
    if (k > N)
        return 0;
 
    if (D[k] != -1)
        return D[k];
 
    D[k] = 0;
 
    if (k + 1 <= N+1)
        D[k] = go(k + 1);
 
    if (k + T[k] <= N+1)
        D[k] = max(D[k], P[k] + go(k + T[k]));
 
    return D[k];
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> T[i] >> P[i];
    for (int i = 1; i <= MAX; i++)
        D[i] = -1;
 
    cout << go(1) << endl;
 
    return 0;
}