14501: 퇴사

문제

• https://www.acmicpc.net/problem/14501
• 입사를 위해 푸는 문제에 퇴사라 크흠

핵심

• 솔직히 이걸 한 1-2주 지나서 다시 풀라고 하면 못풀지도..
• 문제 자체를 보면
  • "오늘" 일을 하면, 오늘 날짜 + 걸리는 시간 째에 돈을 받게 된다.
    • 즉, 오늘이 = 1일이고 걸리는 시간이 3일이면, 4일째에 돈을 받게 된다.
    • 그렇다면, 4일째 기준으로 4일까지 했던 가치와, 오늘 일 하고 받는 돈을 비교해서 업데이트
  • 오늘 일을 하지 않게 되면
    • 다음날 받는 돈은 현재까지 누적된 가치 혹은 다음날 예상되는 값어치를 업데이트 하면 된다.

표

대충 이렇게 입력이 들어왔다고 했을 때, 문제에서 원하는 값은 당연히 200입니다. 하루 일하고 200만원 받는거죠.

자, 한번 1일차부터 5일차까지 쭉 둘러보면

Before

• DP의 인덱스는 1부터 시작하며, N+1개만큼 있습니다.
• 모든 DP원소는 초기 0으로 초기화 되어 있습니다.
• N = 3

1일차

• 이 날에 일을 한 경우

currentDate = 1, time = 1, value = 3
expectedMoneyDate = currentDate + time
dp[expectedMoneyDate] = max(dp[expectedMoneyDate], dp[currentDate] + value[currentDate]

--> 결과
expectedMoneyDate = 2
dp[2] = max(0, 0 + 3) -> dp[2] = max(0, 3) -> dp[2] = 3

• 이 날에 일을 하지 않은 경우

currentDate = 1, time = 1, value = 3
dp[currentDate+1] = max(dp[currentDate+1], dp[currentDate])

--> 결과
dp[2] = max(3, 0) -> dp[2] = 3

2일차

• 이 날에 일을 한 경우

currentDate = 2, time = 2, value = 200
expectedMoneyDate = currentDate + time
dp[expectedMoneyDate] = max(dp[expectedMoneyDate], dp[currentDate] + value[currentDate]

--> 결과
expectedMoneyDate = 4
dp[4] = max(0, 3 + 200) -> dp[4] = max(0, 203) -> dp[4] = 203

• 이 날에 일을 하지 않은 경우

currentDate = 2, time = 2, value = 200
dp[currentDate+1] = max(dp[currentDate+1], dp[currentDate])

--> 결과
dp[3] = max(0, 3) -> dp[3] = 3

3일차

• 이 날에 일을 한 경우

currentDate = 3, time = 4, value = 3
expectedMoneyDate = currentDate + time
dp[expectedMoneyDate] = max(dp[expectedMoneyDate], dp[currentDate] + value[currentDate]

--> 결과
expectedMoneyDate = 7
-- > (expectedMoneyDate <= 4) 조건 위배 --> 실행하지 않음

• 이 날에 일을 하지 않은 경우

currentDate = 3, time = 4, value = 3
dp[currentDate+1] = max(dp[currentDate+1], dp[currentDate])

--> 결과
dp[4] = max(203, 3) -> dp[4] = 203

최종

N일에 일이 끝나야지 돈을 받으니까 돈은 N+1날에 받는다.
dp[N+1]의 값이 답!

코드

#include <iostream>
#include <vector>

using namespace std;

int n;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    vector<int> take_time(n+2, 0);
    vector<int> value_money(n+2, 0);
    vector<int> dp(n+2, 0);

    for (int i = 1; i <= n; i++) {
        cin >> take_time[i] >> value_money[i];
    }

    for (int i = 1; i <= n; i++) {
        // to work today
        if (take_time[i] + i <= n + 1) {
            dp[take_time[i]+i] = max(dp[take_time[i]+i], dp[i] + value_money[i]);
        }

        // If we are not working now
        dp[i+1] = max(dp[i+1], dp[i]);
    }

    cout << dp[n+1] << endl;
}