[BOJ/C++] 14501 퇴사

아이디어를 떠올리는 것이 어려웠던 문제입니다.

동적 계획법을 이용해 문제를 해결할 수 있습니다.

$DP[i]$는 $i$일 까지 얻을 수 있는 최대 수익입니다.

특이한 건 거꾸로 N일부터 구해나갑니다.

$DP[N+1]$의 초기값은 0입니다.

7일로 예시를 들면 일+시간(7+2) > N+1 이므로 퇴사일까지 상담을 끝낼 수 없습니다.

만약 상담을 끝낼 수 없다면 다음 점화식으로 업데이트 합니다.

$DP[i] = DP[i+1]$

5일에서는 5+2 <= N+1 이므로 퇴사일 전에 상담을 끝낼 수 있습니다.

상담을 끝낼 수 있다면 다음 점화식으로 업데이트 합니다

$DP[i] = max(DP[i+1], DP[i+T[i]] + P[i]$

$DP[i+T[i]] + P[i]$는 $i$번째 상담이 끝난 후 다음 상담 + $i$일에 얻을 수 있는 상담 수익입니다.

$DP[i+1]$과 더 큰 수익을 얻을 수 있는 상담으로 업데이트 합니다.

2일로 예시를 들면 2+5 <= N+1 이므로 퇴사일 전에 상담을 끝낼 수 있습니다

$DP[2] = max(DP[2+5] + 20, DP[3])$

$DP[2] = max(20, 45)$

즉 2일에 상담과 7일 상담은 퇴사일전에 가능하지만 3일에 하는 상담이 수익이 더 높아 2일 상담은 안하는게 좋습니다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

static int DP[17] = {};
static int T[16] = {};
static int P[16] = {};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    for(int i=1; i<=N; i++)
        cin >> T[i] >> P[i];

    for(int i=N; i>0; i--)
    {
        if (i + T[i] > N+1)
            DP[i] = DP[i + 1];
        else
            DP[i] = max(DP[i + 1], DP[i + T[i]] + P[i]);
    }
    
    cout << DP[1];

    return 0;
}