[백준] 순회강연

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

2109번: 순회강연

정렬과 우선순위 큐를 활용한 그리디 문제입니다. 각 날짜별로 페이를 집어넣은 다음 페이가 큰 순서로 내림차순으로 정렬해줍니다. 다음으로 날짜순으로 탐색을 시작합니다. 우선순위 큐의 역할은 현재 날짜까지 받은 페이중 가장 작은 값이 먼저 나오도록 하는 min heap입니다. 큐의 크기는 현재 날짜와 최대한 일치하도록 해야합니다. 예를 들어 현재가 10일이면 10일동안 강연이 가능하므로 강연의 수가 부족한게 아니라면 큐의 크기는 10이 되도록 만듭니다. 다음으로는 현재날짜에서 얻을 수 있는 최대 페이를 받도록 해야합니다. 큐의 크기는 현재 날짜와 같으므로 min heap의 top(기존 강연의 페이)와 지금 받을 수 있는 페이를 비교해서 지금 받을 수 있는 페이가 더 크다면 큐에서 하나를  빼 버리고 현재 페이를 집어넣어주면 됩니다. 

 

import sys, heapq
from collections import defaultdict

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())
dict = defaultdict(list)

for _ in range(n):
    p, d = tuple(map(int, input().split()))
    dict[d].append(p)

for key in dict:
    dict[key].sort(reverse=True)

q = []

sorted_key = sorted(dict.keys())

for key in sorted_key:
    pays = dict[key]
    index = 0

    # 현재 날짜까지의 할 수 있는 모든 강연을 가장 큰 순서로 넣어준다.
    while len(q) < key and index < len(pays):
        heapq.heappush(q, pays[index])
        index += 1

    if index == len(pays):
        continue

    # 기존 강연보다 현재 강연의 페이가 더 쎈 경우
    while index < len(pays) and q[0] < pays[index]:
        heapq.heappop(q)
        heapq.heappush(q, pays[index])
        index += 1

print(sum(q))