[BaekJoon] 백준 14501번 : 퇴사

14501번 : 퇴사

DP 배열에 총 상담 가격을 저장하며 i 일에 상담하는 가격과 i + T[i] - 1 일 이후 부터의 최대 가격을 더하면 된다.

위의 표를 통해 예를 들자면 4 일에 상담을 하는 경우 4 일의 상담가격과 5일, 6일, 7일 의 상담가격 중 최대를 더하면 된다.

---

import sys


def solution():
	dp = [0 for _ in range(n + 1)]

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

	return max(dp)


if __name__ == "__main__":
	n = int(input())
	t, p = [0], [0]

	for _ in range(n):
		time, cost = map(int, sys.stdin.readline().rsplit())
		t.append(time)
		p.append(cost)

	print(solution())