[BaekJoon] 백준 15486번 : 퇴사2

15486번 : 퇴사2

[BaekJoon] 백준 14501번 : 퇴사 문제와 똑같지만 입력되는 데이터의 최대 개수가 1,500,000 개로 늘어났다.

때문에 매번 최댓값을 구해서 계산하는 14501번의 풀이는 시간초과가 발생한다.

최댓값을 계속 구하지 말고 저장해서 바로바로 사용 할 필요가 있다.

DP 문제를 풀 때마다 느끼는데 최댓값을 구하는 경우 최댓값 정보를 계속 가지고 있으면서 갱신해주는 작업이 필요하다.

그런데 이 과정을 생각하는게 너무 어렵다..

---

import sys


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

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

	return max_cost


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

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

	print(solution())