[백준] 2109번 > 순회강연

www.acmicpc.net/problem/2109

2109번: 순회강연

문제

한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

출력

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

---

풀이

최소 힙을 만들고 날짜를 기준으로 오름차순 정렬을 한다. (동일하면 pay 내림차순)

for문을 돌면서 heap에 해당요청의 pay를 push한다. 그 후 힙의 크기가 해당 요청의 날짜보다 크다면 그 요청은 이루어질 수 없기 때문에 pop해준다. 이런식으로 for문을 돌고나서 모든 원소들을 더해주면 최댓값이 된다.

import sys
import heapq
input = sys.stdin.readline
n = int(input())
lectures = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: (x[1], -x[0]))
queue = []
for i in lectures:
    heapq.heappush(queue, i[0])
    if len(queue) > i[1]:
        heapq.heappop(queue)
print(sum(queue))