백준 13904번 : 과제 in Python

13904번: 과제

 

www.acmicpc.net

이 문제는 각 과제의 점수와 마감 기한이 주어질 때 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 단, 과제는 하루에 하나씩만 끝낼 수 있다.

각 과제는 마감 기한이 다를 뿐이지 각 과제를 해결하는데 걸리는 시간은 모두 하루로 동일하므로 되도록이면 점수가 높은 과제를 해결하는 것이 좋을 것이다. 단, 마감 기한이 짧은 과제도 충분히 고려할 수 있도록 마감 기한이 긴 과제는 되도록 나중에 해결해야 한다. 

이를 코드로 구현하기 위해, 우선 min-heap을 만들고 여기에 N개의 input을 넣는데, 만약 마감 기한 d와 점수 w가 주어지면 [-w, -d]를 heap에 넣는다. 즉, 과제의 점수가 큰 순서대로, 만약 점수가 같은 경우에는 과제의 마감 기한이 늦은 순서대로 저장한다. 그 다음 얻을 수 있는 점수가 최대가 될 때 각 날짜마다 해결한 과제의 점수를 저장하는, 길이가 1001인 배열 res를 만든다.

이제 heap에서 가장 점수가 높은 과제를 하나씩 뽑아 그 과제를 마감 기한 내에 해결할 수 있는 경우에만 이를 res 배열에 저장한다. 이를 위해 그 과제를 최대한 늦게 해결해 마감 기한이 빠른 과제도 고려할 수 있게 해야 하므로 과제의 마감 기한 d에서 시작해 res의 d번째 entry가 0이 되기 전까지 d를 하나씩 줄이고, d번째 entry가 0이 되면 이를 res의 d번째 entry에 저장한다. 만약 d가 0이 될 때까지 res의 d번째 성분이 0이 되지 않는다면 해당 마감 기한까지의 모든 날짜에 해결할 과제가 남아있음을 의미하므로 그 과제는 해결할 수 없다. 

이를 heap이 빌 때까지 반복하면 res에는 점수가 최대가 될 때 각 날짜에 해결할 과제의 점수가 저장된다. 이제 res에 저장된 모든 점수를 더하면 얻을 수 있는 점수의 최댓값을 얻을 수 있다.

이를 코드로 구현하면 다음과 같다.

import heapq
N = int(input())
heap = []
for _ in range(N):
    d, w = map(int, input().split())
    # min-heap을 max-heap으로 구현하기 위해 부호를 반대로 한다.
    heapq.heappush(heap, [-w, -d])
res = [0 for _ in range(1001)]
while heap:
    w, d = heapq.heappop(heap)
    w = -w; d = -d
    while d > 0:
        if res[d] == 0:
            res[d] = w
            break
        d -= 1
print(sum(res))