대충 이렇게 입력이 들어왔다고 했을 때, 문제에서 원하는 값은 당연히 200입니다. 하루 일하고 200만원 받는거죠.
i | 1 | 2 | 3 |
---|---|---|---|
Time | 1 | 2 | 4 |
Value | 3 | 200 | 3 |
자, 한번 1일차부터 5일차까지 쭉 둘러보면
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
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
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;
}