[백준] 14501번(python 파이썬) 퇴사

728x90

n = int(input())
t = [0] * (n + 1)
p = [0] * (n + 1)
dp = [0] * (n + 1)
for i in range(n):
    t[i], p[i] = map(int, input().split())

for i in range(n - 1, -1, -1): #거꾸로
    if t[i] + i > n: # 현재 날짜에 상담 일수를 더했을때 n보다 크면 불가능
        dp[i] = dp[i + 1] # 맨 마지막이 0이기 때문에 불가능하면 계속 0
    else:
        dp[i] = max(p[i] + dp[t[i] + i], dp[i + 1]) # 옆에 것과 더할 수 있는 합중에 큰것을 저장
print(dp[0])
    

앞에서부터 보는것이 아니라 뒤에서부터 보면 되는 문제이다.

아래는 내가 이해한걸 기억하기 위해 그려둔 설명이다.