[Python] 퇴사 - 백준 (DP)

해당 글은 백준 14501번 문제 '퇴사'를 다룬다.

문제

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

14501번: 퇴사

 

설명

해당 문제는 동적 계획법으로 Top-Down 형태로 풀 수 있다.

i일에 상담할 때

- 퇴사일을 넘긴다면, 상담을 하지 않고

- 퇴사일을 넘기지 않는다면, i일에 상담을 하지 않는 것과 상담을 하는 것 중 max 값을 선택한다.

 

 

코드

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

dp = [0]*(n+1)

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