[백준] 14501: 퇴사 파이썬 리뷰

14501번: 퇴사

풀이는 해당 블로그를 참고했습니다.

 

dp 계산을 N부터 시작하는 방법을 사용해야 했습니다. 뒤에서 부터 계산을 해보면 다른 동적 계획법과 풀이 방법은 비슷합니다.

 

파이썬 코드

import sys
readline = sys.stdin.readline

N = int(readline())
T, P = [], []
for _ in range(N):
    t, p = map(int, readline().split())
    T.append(t)
    P.append(p)

d = [0] * (N+1)

for i in range(N - 1, -1, -1):
    # i일에 상담을 하는 것이 퇴사일을 넘기면 상담을 하지 않음
    if i + T[i] > N:
        d[i] = d[i+1]
    else:
        # i일에 상담을 하는 것과 상담을 안하는 것 중 큰 것을 선택
        d[i] = max(d[i+1], P[i] + d[i + T[i]])

print(d[0])