[실버4] 14501번 : 퇴사

🛠 문제

https://www.acmicpc.net/problem/14501

👩🏻‍💻 해결 방법

리스트를 뒤에서부터 확인하면서 해당시간 i에서 t[i]만큼 시간이 흘렀을 때, 값이 n보다 작거나 같으면 dp 점화식에 따라 최고 이익을 갱신해주었다

소스 코드

n = int(input())
t = []
p = []
dp = [0] * (n + 1)
max_value = 0

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

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

print(max_value)