문제링크 : 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)