[백준] 13904번 과제(파이썬)

문제링크 : https://www.acmicpc.net/problem/13904

난이도 : GOLD III

문제

하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

문제 해결

• 최대힙을 사용하는 문제이다.
• 마감일을 기준으로 마지막 일수 부터 역순으로 정렬하고
• 해당 일에 대응 하는 value 값을 최대 힙에 저장한다.
• 매 일 마다 heapq.heappop() 값을 더해준다.

소스코드

import heapq
import sys

input = sys.stdin.readline

n = int(input())

tasks = []
h = [] # heap 생성
ans = 0
for _ in range(n):
    a, b = map(int, input().split())

    tasks.append((a, b))

tasks.sort(key=lambda x: x[0]) #마감일을 기준으로 오름차순정렬

for date in range(tasks[-1][0], 0, -1):
    while tasks and tasks[-1][0] >= date:
        heapq.heappush(h, -tasks.pop()[1]) #최대힙 생성

    if h:
        ans -= heapq.heappop(h)

print(ans)