20210622#(45) 백준 14501 퇴사 (다이나믹 프로그래밍)

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

14501번: 퇴사

 

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

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

 

 

다이나믹프로그래밍 공부를 위해 풀어본 문제.. 제목이 재밌어보여서 품

dp문제를 풀때는 점화식을 잘 찾아내면 되는데 이번 문제에선 생각보다 어려웠다.

거꾸로 탐색한다는 생각만 할 수 있다면 수월하게 풀었을만한 문제이다.