[C++] 백준 14501번 : 퇴사

문제

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

최대 수입을 가져갈 수 있도록 한다.

점화식

d[i] : i번째 날부터 퇴사일까지 벌 수 있는 최대 수입

i + day <= n :  d[i] = max(d[i + day] + value, d[i + 1])
else : d[i] = d[i + 1]

 

즉, 가장 마지막날 시작하는 작업부터 ~ 첫날 시작하는 작업 순으로 확인하면서,
기존의 이벤트를 유지하는 게 더 효율적일지,
아니면 새 이벤트를 추가하는 것이 더 효율적일지를 확인한다.

 

만약, [ 작업 시작일 + 작업 소요 시간 ] > [ 퇴사일 ] 이라면, 수행할 수 없는 작업이므로,
(i+1)번 째 날부터 퇴사까지에 벌 수 있는 수입과 (i)번째 날부ㅌ 퇴사까지에 벌 수 있는 수입과 동일하게 된다.

 

만약, [ 작업 시작일 + 작업 소요 시간 ] <= [ 퇴사일 ] 이라면, 수행할 수 있는 작업이므로,
해당 작업을 추가했을 때의 수입과 추가하지 않았을 때의 수입을 비교하여 더 큰 수입을 가져갈 수 있도록 한다.

 

이때, 새로운 작업이 추가되는데, 작업은 수요시간이 들기 때문에, 그 만큼의 소요 시간을 여유로 둬야한다.

따라서, d[i] = max(d[i + day] + value, d[i + 1]) 와 같은 점화식이 만들어지게 된 것이다.

풀이

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    vector<pair<int, int>> work;

    for (int i = 0; i < n; i++)
    {
        int day, value;
        cin >> day >> value;
        work.push_back({day, value});
    }

    vector<int> d(n + 1, 0);

    for (int i = n - 1; i >= 0; i--)
    {
        auto [day, value] = work[i];

        // 만약 작업이 퇴사일까지 가능하다면
        if (i + day <= n)
        {
            d[i] = max(d[i + day] + value, d[i + 1]);
        }
        else
        {
            // 만약 작업이 퇴사일 까지 불가능하다면
            d[i] = d[i + 1];
        }
    }

    cout << d[0];
}