[Python] boj no. 14501 : 퇴사

Problem

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

Idea

다음과 같은 기준으로 동적 계획법을 이용해 해결했다.

1. N번째 날까지의 최대 수익 값을 dp[N]이라고 하면, 기본적으로 dp[N] = dp[N-1]이다.
2. 만약 k번째 날에 시작해서 N번째 날에 끝나는 비용이 v인 상담이 있다면 dp[N] = max(dp[N-1], dp[k]+v)이다.

Code

import sys
import heapq

input = sys.stdin.readline

N = int(input())
dp = [0 for _ in range(N+2)]
heap = []

for i in range(1, N+2):
    if i != N+1:
        T, P = map(int, input().split())
        heapq.heappush(heap, (i+T, i, P))
    
    mv = dp[i-1]
    while heap and heap[0][0] <= i:
        end, start, value = heapq.heappop(heap)
        mv = max(mv, dp[start] + value)
        
    dp[i] = mv
    
print(dp[N+1])

Comment