[백준 15486] 퇴사 2, C++

https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

 본 문제는 퇴사와 조건은 똑같다. 차이는 입력의 크기가 퇴사는 15, 퇴사 2는 1,500,000으로 퇴사 소스코드로 퇴사 2를 풀 수 없다. 퇴사할 때까지 최대로 많은 이익을 얻으려면 퇴사 전까지 많은 이득을 얻어야 하기 때문에 큰 문제를 작은 문제로 해결할 수 있다. 그리고 계산의 반복이 있다. 따라서, DP로 문제 해결이 가능하다. 

이 문제는 선택 여부에 따라 도착 지점의 값을 비교해야 한다. 문제 해결 과정은 다음과 같다.

1. i 번 째 일을 할 때 : i+T(i)
2. i 번 째 일을 안 할 때 : i+1
3. 이때, i 번 이전에서 일을 하여 i+1, i+T(i)에 도착할 수 있기 때문에 값을 비교한다.
4. 즉, d[i+T(i)] = max(d [i+T(i)], d [i] + P(i)),
5. d [i+1] = max(d [i+1], d [i])로 점화식을 정의할 수 있다.

#include <cstdio>
#include <vector>
 
using namespace std;
 
int d[1600000];
vector<pair<int, int>> v;
int n;
int ans = 0;
 
int main() {
    scanf("%d", &n);
    v.push_back(make_pair(0, 0));
    for (int i = 1; i <= n; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        v.push_back(make_pair(x, y));
    }
    for (int i = 1; i <= n; i++) {
        d[i+v[i].first] = max(d[i+v[i].first], d[i] + v[i].second);
        d[i+1] = max(d[i+1], d[i]);
    }
    printf("%d\n", d[n+1]);
}