BOJ : 14501 퇴사 (파이썬)

문제

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

14501번: 퇴사

이 문제는 다이나믹 프로그래밍 기법으로 풀 수 있는 문제이다.

중요한 점은 for문을 1부터 시작했으면 d[n]에 해당하는 값들이 다 0 으로 되어있기 때문에 그 당일날 보상만 계산이 되기 때문에 뒤에서부터 for문을 돌렸다.

import sys

n = int(sys.stdin.readline())

d=[0] * (n+1)

#t는 시간 p는 보상
lstt = []
lstp = []
for _ in range(n) :
    t,p = map(int, sys.stdin.readline().split())
    lstt.append(t)
    lstp.append(p)

for i in range(n-1,-1,-1) :
    if lstt[i] + i <= n :
        d[i] = max(d[i+1] , lstp[i] + d[i+lstt[i]])
    else :
        d[i] = d[i+1]


print(d[0])