DP - 15486번: 퇴사 2

• dp[i]: i일 전까지 얻을 수 있는 최대 수익
• dp[i] = max(dp[i], dp[i-1])로 당일 상담을 안 했을 때 전일 수익을 받아오기
• 상담 가능 기간(i + times[i])이 범위 안이면
  -> dp[i + times[i]] = max(dp[i + times[i]], dp[i] + profits[i])로 수익을 갱신

import sys
input = sys.stdin.readline

n = int(input())

times = [-1]
profits = [-1]

for _ in range(n):
    t, p = map(int, input().split())
    times.append(t)
    profits.append(p)



dp = [0] * (n + 2)

for i in range(1, n + 1):

    dp[i] = max(dp[i], dp[i - 1])
    
    if i + times[i] <= n + 1:
        dp[i + times[i]] = max(dp[i + times[i]], dp[i] + profits[i])
    
        #print(i, dp[i])

dp[n + 1] = max(dp[n], dp[n + 1])


print(dp[n + 1])