[백준] 13904번 과제 (Python)

백준 13904 과제

아이디어는 떠올랐지만 시간 초과가 날 것 같아 망설였다. 우선순위를 활용한 그리디알고리즘 문제다. 이 문제에서 중요한 포인트는 이와 같다.

1. 모든 과제의 시작일은 동일해서 끝나는 일만 고려하면 된다.
2. 과제가 끝나는 일자에 최대한 맞춰서 끝낸다면 더욱 많은 과제를 선택할 수 있다. (시작하는 날짜는 0일로 똑같기 때문)

이러한 특성을 토대로 만든 문제 솔루션은 이와 같다.

1. 점수를 기준으로 내림차순으로 정렬한다.
2. 해당하는 점수를 얻되, 더욱 많은 과제를 선택할 수 있도록 마감 일자에 맞춰 선택한다.
3. 마감 일자에 다른 과제를 이미 선정했다면 하루씩 앞당겨 해당 일에 과제를 할 수 있는지 확인한다.

import sys
from collections import defaultdict
import heapq
n = int(sys.stdin.readline())
h = []

dd = defaultdict(int)

for _ in range(n):
    d, w = map(int, sys.stdin.readline().split())
    heapq.heappush(h, [-w, -d])
res = 0
while h:
    w, d =  [ -x for x in heapq.heappop(h)]
    while(dd[d] != 0 and d > 0):
        d -= 1
    if d != 0:
        dd[d] = w
        res += w
print(res)