[백준/파이썬] #15486

30분 타임어택을 하지는 못했지만, 대략적인 방법까지는 유추해냈다. 참고한 풀이와 비슷하게 DP 배열을 선언하고, 첫째 날부터 마지막 날까지의 각 날마다 얻을 수 있는 최대 상담료를 계산하면 되었다. 

import sys

input = sys.stdin.readline

N = int(input())
DP = [0] * (N+1)
time = [0] * (N+1)
price = [0] * (N+1)
for i in range(1, N+1):
    T, P = map(int, input().split())
    time[i] = T
    price[i] = P

for i in range(1, N+1):
    DP[i] = max(DP[i], DP[i-1])
    end_date = i + time[i] - 1
    if end_date <= N:
        DP[end_date] = max(DP[end_date], DP[i-1] + price[i])

print(DP[N])