BOJ(백준) 14501번 퇴사 파이썬

14501번: 퇴사

---

코드

import sys
r = sys.stdin.readline
N,*l=int(r()),
for _ in range(N):
    l.append(list(map(int,r().split())))

max_pay = 0
dp = [0]*(N+1)

for i in range(N-1,-1,-1):
    if i+l[i][0] > N:
        dp[i] = max_pay
    else:
        dp[i] = max(l[i][1] + dp[i+l[i][0]], max_pay)
        max_pay = dp[i]
print(max_pay)

 

해설

처음에 dp에 어떤 값을 저장해야 할지에 대해 고민을 많이 했습니다. 처음에는 그 특정 상담 일정까지 벌 수 있는 수입의 최댓값을 저장하려고 했지만 구현이 쉽지 않았습니다. 특정 상담일부터의 최대 이익을 저장하기로 정했고 이를 위해서 마지막날부터 역으로 순회하게 포문을 구현했습니다.

 

결과