[BOJ 14501, 15486] 퇴사1, 퇴사2

#include <bits/stdc++.h>
using namespace std;
int N, T[1500001], P[1500001];
int dp[1500001];
int ans;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++) {
        cin >> T[i] >> P[i];
        dp[i] = P[i];
    }
    for(int i = N; i > 0; i--) {
        if(T[i] + i > N + 1) dp[i] = dp[i + 1];
        else dp[i] = max(dp[i+1], P[i] + dp[i+T[i]]);
    }
    cout << dp[1];
}

$O(N)$ 에 하는 방법을 찾으면 둘 다 똑같이 풀 수 있다.

$D[i]$ 를 $i$일 까지 일 했을 때 얻을 수 있는 최대 이득이라고 하면, 현재 $i$ 일의 일을 안 할수도 있고 할 수도 있기 때문에, 이걸 케이스로 두 가지로 나눠 max를 따져 보면 된다. 안 하면 다음 날짜인 $D[i+1]$ 을 보면 되고, 일을 하면 $D[i+T[i]] + P[i]$ 를 보면 되기 때문에, 두 값에 대해 max를 취하면 된다. 이걸 역순으로 보면 $D[i]$ 에 대해서 풀 수 있다.

그리고 퇴사1 에선 N의 범위가 작아 dfs로 풀 수 있는데, 퇴사2에선 범위가 커지기 때문에 메모이제이션을 적용하여 dfs에서 쓴 재귀식을 그대로 사용할 수 있다.