problem-14501

과정
1. dp를 마지막날부터 역순으로 찾아감

2가지 경우의 수
1. i번째 날에 상담을 하게되면 n일안에 끝내지 못할 경우
-> 상담불가능 dp[i]=dp[i+1]
2. i번째 날에 상담이 가능한 경우
-> dp[i]=max(dp[i+1],dp[i+t]+p). **여기서 t는 i번째 상담이 걸리는 시간, p는 그 상담을 함으로써 얻는 이득

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

for i in range(n-1,-1,-1):
    t,p=tp[i]
    if t+i>n:
        dp[i]=dp[i+1]
    else:
        dp[i]=max(dp[i+1],dp[i+t]+p)

print(max(dp))

time:40분