[백준] 14501: 퇴사

#DP

퇴사

d[i]: i 번째 날 상담을 시작했을 때 백준이가 얻을 수 있는 최대 수익
t[i] : 상담에 걸리는 일 수
p[i] : 상담을 하면 받을 수 있는 보수

n의 범위가 1~ 15이고 t의 범위가 1~5 이므로 d는 20까지 0으로 초기화해놓은 후 점화식을 세웁니다.
맨 끝에서부터 시작하는 것이 핵심입니다. 왜냐하면 가정대로 라면 i가 커질수록 얻을 수 있는 값이 작아지기 때문입니다.

해당날에 얻을 수 있는 최대 수익은 오늘 건너뛰고 내일부터의 최대 수익과
오늘 얻을 수 있는수익 + 다음 상담날 부터의 최대 수익을 더한 것을 비교하면 됩니다.
d[i] = max(d[i+1] , d[i+t[i]] + p[i])
그리고 i + t[i] 가 인덱스를 넘어가면 그 다음날의 수익이 최대 이므로
d[i] = d[i+1] 이 됩니다.

'''
d[i] = max(d[i+1] , p[i] + d[i+t[i])

'''

import sys
input = sys.stdin.readline
n = int(input())
t = []
p = []
t = [0] + t
p = [0] + p
for i in range(n):
	a, b = map(int, input().split())
	t.append(a)
	p.append(b)

d = [0] * 21
for i in range(n, 0, -1):
	if (i + t[i]) > n+1:
		d[i] = d[i+1]
	else:
		d[i] = max(d[i+1], d[i+t[i]] + p[i])

print(d[1])