[백준][Python] 15486번 퇴사 2

15486번: 퇴사 2

 

 

 

코드

import sys

n = int(input())
T = [0]*(n+2)
P = [0]*(n+2)
dp = [0]*(n+2)
for i in range(1,n+1):
    T[i],P[i] = map(int,sys.stdin.readline().split())

for i in range(1,n+1):
    if(i+T[i] <= n+1):
        dp[i+T[i]] = max(dp[i+T[i]],dp[i]+P[i])
    dp[i+1] = max(dp[i+1],dp[i])

print(max(dp))

 

설명

n+1일에 끝나는 상담은 할 수 있다. 

만약 1일에 잡힌 상담을 한다면 dp[i+T[i]] 인 dp[4]의 값은 10이 된다. 이런 식으로 최댓값을 갱신해나가면 된다. 

마지막에 dp[i+1] = max(dp[i+1], dp[i]) 를 해주는 이유는 다른 경로를 통해 오는 것보다 그 전날 상담을 하지 않고 다음날로 넘어오는 것의 금액이 더 큰 경우가 존재하기 때문이다.