[백준 c++] 14501 퇴사

---

문제

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

1일부터 N일까지의 상담 소요기간, 받는 금액이 입력으로 주어진다.
하루에 상담은 1건만 할 수 있다.
N+1일에 퇴사를 한다고 할 때, N일 동안 얻을 수 있는 최대 이익을 구하는 문제다.

예를 들어 1일에 3일이 걸리는 상담을 하면 2일, 3일에는 다른 상담을 할 수 없다.

---

풀이

실버3이지만 어려웠다..뭔가 dp를 이용하는건 맞는거 같은데 dp에 어떻게 저장할지 감이 안왔달까ㅜ


뒤에 나오는 값에 따라 최대 이익이 바뀌기 때문에 마지막날부터 역순으로 생각하면 된다.


만약 3일째 날에 2일이 소요되고 50원 받는 상담을 할 수 있다면 이 날 상담할 것인지 아닌지를 선택해야한다.


상담하기로 선택한다면 얻을 수 있는 이익은 50원 + 5일째 날에 얻은 이익
상담하지 않는다면 3일째까지 얻은 이익은 여전히 4일째 날에 얻은 이익


이것을 dp로 점화식을 세울 수 있다.
dp[i] = max(dp[i + 1], p[i] + dp[i + t[i]]

---

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, t[16], p[16], dp[21];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> t[i] >> p[i];

    for (int i = n; i >= 1; i--)
    {
        if (i + t[i] - 1 > n)
            dp[i] = dp[i + 1];
        else
            dp[i] = max(dp[i + 1], p[i] + dp[i + t[i]]);
    }
    cout << dp[1] << "\n";
}