[python/파이썬] 백준 14501 퇴사

[문제 출처]

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

14501번: 퇴사

 

[문제 풀이]

퇴사 전 n일 동안 최대한 많은 금액을 받을 수 있는 일정을 짜는 문제이다.

n일동안 매일 상담이 잡혀있으며 각 상담은 걸리는 시간과 상담 후에 받는 금액이 다르다.

n일 이후에는 상담을 할 수 없으므로

 

dp를 0부터 채워나가기보다는 n-1부터 채워가는 것이 좋다.

n-1부터 그날의 상담을 선택했을 때 혹은 선택하지 않고 다음날의 상담을 선택했을 때의 금액을 비교하여

더 높은 금액을 받을 수 있는 수 있는 상담을 택한다.

 

import sys
input = sys.stdin.readline

n = int(input())

cons = []
for _ in range(n):
    t, p = map(int, input().split())
    cons.append([t,p])

dp = [0 for _ in range(n+1)]

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

print(dp[0])