[백준 14051] 퇴사

문제 보기

이 문제는 동적계획법(Dynamic Programming) 문제이다.

아주 쉬운 문제이지만, DP에 익숙하지 않아서 고민을 많이 했다.

풀이는 다음과 같다.

1. 내일 벌 돈이 오늘 번 돈보다 적다면 이를 갱신한다.

2. 오늘 일을 하면 오늘로부터 time[i]번째 날에 돈을 받는다.

3. 오늘 일을 해서 time[i]번째날 후에 받을 수 있는 돈이 현재 time[i]번째 날에 받을 수 있는 돈의 최대값보다 크다면 이를 갱신한다.

import sys
 
n = int(sys.stdin.readline())
time = [0 for _ in range(n)]
price = [0 for _ in range(n)]
dp = [0 for _ in range(n + 1)]
for i in range(n):
    time[i], price[i] = map(int, sys.stdin.readline().split())
    
for i in range(n):
    # if sum of the price of today is greater than sum of the price of tomorrow, update the maximum price
    dp[i + 1] = max(dp[i], dp[i + 1])
    
    # if i start to work from today, it will end after time[i] days
    if i + time[i] <= n:
        # compare the current maximum price after time[i] days with the maximum sum of today
        dp[i + time[i]] = max(dp[i + time[i]], dp[i] + price[i])
print(dp[n])