[BOJ] C++ 15486: 퇴사 2 - 테이블링이 어려운 DP

15486번: 퇴사 2

---

이전에 백트래킹으로 푼 문제와 똑같은데 입력의 크기가 많이 큰 문제이다. 이 정도 크기면 O(N^2)은 당연히 안되고 O(N)이나 O(N log N)으로 풀어야 한다. 풀이를 떠올리기 굉장히 힘들었는데, 그리디 하게 풀면 당연히 안되고 dp로 풀자니 테이블링이 쉽지 않았다. 테이블을 앞에서부터 탐색하면서 점화식을 찾으려 했는데 도저히 답이 나오지 않아서 정답을 살짝 참고했다.

 

바킹독님의 풀이에는 테이블링을 뒤에서부터 시작하면서 dp[i] = i일차부터 상담을 시작하는 걸로 정의해서 구현했다. 딱 여기까지만 힌트를 얻고 점화식을 찾았다.

 

배열을 뒤에서부터 탐색하니 점화식이 보였다. i일차 상담을 하는 경우와 하지 않는 경우로 나눠서 최대 이익을 구할 수 있었는데, 상담을 하는 경우 얻는 이득은 dp[i+t[i]] + p[i]이다. dp[i+t[i]]는 i일차 상담이 끝난 시점부터를 시작점으로 한 최대 이익이므로 p[i]만 더해주면 되는 것이다. i일차 상담을 하지 않은 경우는 간단하게 dp[i+1]이 된다. 

 

이렇게 테이블링과 점화식만 잘 짜주면 구현은 쉽다. 다른 dp문제들도 풀다보면 배열을 거꾸로 탐색하면 답이 나오는 경우가 종종 있다. 이번 문제에서는 상담이 끝나는 날이 중요하기에 거기서 힌트를 얻어서 테이블링을 할 수 있었다.

/** DP 15486 퇴사2 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n;
int t[1500010];
int p[1500010];
int dp[1500010];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> t[i] >> p[i];

    fill(dp, dp + n + 3, 0);

    // dp[i] = i일차에 상담 시작 i는 n부터 시작
    for (int i = n; i > 0; i--)
    {
        // i일차의 상담을 할 수 있는 경우
        if (i + t[i] - 1 <= n)
        {
            // i일차의 상담을 한다면 dp[i+t[i]]부터 상담을 할 수 있다.
            // 따라서 i일차의 상담을 한다면 dp[i]는 p[i]+dp[i+t[i]]가 된다.
            // i일차의 상담을 하지 않는다면 dp[i+1]
            dp[i] = max(dp[i + 1], dp[i + t[i]] + p[i]);
        }
        else
        {
            // i일차의 상담을 할 수 없다면 dp[i+1] 그대로 가져오기
            dp[i] = dp[i + 1];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(dp[i], ans);

    cout << ans << '\n';
}