[Baekjoon] 14501번 : 퇴사 (Python, DP)

[Baekjoon] 14501번 : 퇴사 (Python, DP)

 

목차

 

 

 

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

14501번: 퇴사

 

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 30840KB / 시간 68ms / 코드 길이 310B

 

DP 문제로 역순으로 고려해야 한다.

왜냐하면 t가 앞을 고려한 p 값의 최댓값을 구해야 하기 때문이다.

 

n = int(input())
t = []
p = []
dp = []
for i in range(n):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)
    dp.append(b)
dp.append(0)

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