[백준-14501] 퇴사

---

나의 코드

import sys
input = sys.stdin.readline

n=int(input())
graph=[]
for _ in range(n):
    graph.append(list(map(int,input().split())))

dp=[0]*(n+1)
for i in range(n-1,-1,-1):
    if graph[i][0]+i==n:
        dp[i]=graph[i][1]
    elif graph[i][0]+i<n:
        dp[i]=max(dp[graph[i][0]+i:])+graph[i][1]

print(max(dp))

수행시간: 68ms

---

풀이

graph에는 [t,p]가 들어간다.
dp는 n번째날에서 첫번째날로 거꾸로 되돌아가면서 탐색한다.
dp[i]는 i번째날의 상담을 포함하면서 n번째날까지 포함가능한 상담중 최대 수익을 저장한다.
max(dp[graph[i][0]+i:])는 i번째날상담의 끝나는 다음날부터 마지막날까지의 수익중 최대수익이다.