백준 15486 퇴사 2

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

15486번: 퇴사 2

 

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX_NUM 1500001

using namespace std;


//dp[i]: i일에 받을 수 있는 최대 이익


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int n;
    int ans = 0;


    cin >> n;

    vector<pair<int, int>> work(n + 1);
    vector<int> dp(n + 2, 0);

    for (int i = 1; i <= n; i++) {
        cin >> work[i].first >> work[i].second;
    }

    for (int i = 1; i <= n + 1; i++) {
        ans = max(ans, dp[i]);
        //오늘 일을 했을 때 퇴사일을 넘긴다면 일을 할 필요가 없음
        if (i + work[i].first > n + 1) {
            continue;
        }
        //오늘 일을 했을 때 work[i].first일 이후 받는 돈과 일을 하지 않았을 때 받는 돈을 비교
        dp[i + work[i].first] = max(dp[i + work[i].first], ans + work[i].second);

    }

    cout << ans;


    return 0;
}

 

dp[i]: i-1일까지 일하여 i일에 받을 수 있는 최대 액수

 

오늘이 k일이라 한다면 오늘 일을 시작했을 때 work[k].first일이 소요된다.

그리고 k+work[k].first일 후에 work[i].second원이 들어오게 된다.

 

만약 오늘 일을 하지 않는다면 dp[k+work[k].first] 만큼의 돈을 받게 될 것이다.

이 중 최댓값을 구하면 된다.

 

ans 자리에 dp[i]가 오지 않는 이유를 생각해보자.

만약 다음과 같은 일거리가 주어졌다고 가정하자

 

t	2	1
p	100	1

 

3일차에 dp[3]은 전날에 일을 하여 번 1원이 들어오지만

1일차에 일을 하고 2일차를 쉬게 되면 100원이 들어오게 된다.

따라서 항상 최댓값을 갱신해주어야 한다.