[백준] 15486번: 퇴사 2 - python

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

 

아까 푼 퇴사 1하고 뭐가 다른지 잘 모르겠는 문제

 

T, P에 값을 저장한 뒤, 뒤에서부터 값이 딱 퇴사일과 같을 경우에만 dp에 값을 저장하면서 저장시에는 전 날, T전 날 + P 가격과 비교하면서 값을 저장해준다. 만약 값이 퇴사일을 넘을시에는 전에 있던 값을 그대로 옮기면서 첫날까지 오면 첫날에 최대값이 나오게 된다.

n = int(input())
T = []
P = []
dp = [0] * (n+1)
for _ in range(n):
    a, b = map(int, input().split())
    T.append(a)
    P.append(b)

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

print(dp[0])

 

완성