#include <iostream>
#include <algorithm>
using namespace std;
int a[15000002];
int p[15000002];

int t[15000002];

int main(void)
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> p[i];
        ;
    }

    for (int i = 1; i <= n; i++)
    {
        // 상담할 때 ,
        if (i + a[i] <= n + 1)
        {
            t[i + a[i]] = max(t[i + a[i]], t[i] + p[i]);
        }
        // 상담 안할때,
        if (i + 1 <= n + 1)
        {
            t[i + 1] = max(t[i + 1], t[i]);
        }
    }
    cout << t[n + 1];
    return 0;
}

해결 방법

DP 문제로 해결한다.n이 15000000 까지 가므로, 기존에 이용한 o(n^2) 시간복잡도 해결 방법으로는 풀리지 않았다. 상담을 할 때와 상담을 안할때를 구분하여 구한다.
t[i] = i 날 까지 왔을 때 최대 이익이므로, 상담을 하게된다면 t[i+a[i]] 날로 갈것이고, 만약 안한다면 t[i+1] 날로 갈것이다. 케이스를 나누어서 생각하면 된다.