14501: 퇴사

문제

핵심

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

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

i123
Time124
Value32003

자, 한번 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;
}

좋은 웹페이지 즐겨찾기