[백준] 퇴사

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

14501번: 퇴사

 

동적계획법으로 역순으로 dp[i] 를 정하였다. (dp[i] = i일부터 N일까지 일했을 때의 최대 이익)

 

걸리는 기간을 포함한 날짜가 N일을 넘어가면 일을 할 수 없는 경우이므로 dp[i] = dp[i+1]

일을 할 수 있는 경우에는 i일에 일을 하지 않았을 때와 i일에 일을 했을 때 중 최댓값을 dp[i] 로 설정한다.

 

i 일에 일을 하지 않았을 때 : dp[i+1] (i+1일부터 N일까지 일했을 때의 최대 이익)

i 일에 일을 했을 때 : p + dp[i+t] (i일에 일을 했을 때 얻는 이익 + (i+t)일부터 N일까지 일을 했을 때 얻는 이익)

 

import sys

N = int(sys.stdin.readline())
jobs = [] 

for i in range(N):
    jobs.append(list(map(int, sys.stdin.readline().split())))

jobs.reverse()

dp = [0] * (N + 2)
for i, job in zip(range(N, 0, -1), jobs):
    t, p = job
    
    if i + t - 1 > N:
        dp[i] = dp[i+1]
    else:
        dp[i] = max(p + dp[i + t], dp[i+1]) 

print(dp[1])