[동적계획법] 백준 14501번 '퇴사' (Python)

<문제 링크>

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

14501번: 퇴사

---

<문제 풀이>

1. 리스트 뒤에서부터 거꾸로 확인

 

<코드>

#이취코 답
n = int(input())
t = []
p = []
dp = [0] * (n+1)
max_value = 0

for i in range(n):
    a,b = map(int,input().split())
    t.append(a)
    p.append(b)
    
for i in range(n-1, -1, -1):
	time = t[i]+i
    if time<=n:
    	dp[i] = max(p[i]+dp[time], max_value)
        max_value = dp[i]
    else:
    	dp[i] = max_value
        
print(max_value)

 

<고쳐야 할 점>

• 해당 풀이 기억하기
• 중간 과정이 더 클 수 있다는 점 ,,,
• 복습 알고리즘