[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 2109번 _ 순회강연

https://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값이 주어진다.

[출력]

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

 

[아이디어]

1) "13904번 과제"와 거의 동일한 문제다.

2) 더 많은 강연료를 주는 강의부터 차례로 담으면서, 가능한 강의 날짜보다 담은 개수가 많아질 때마다 가장 우선순위가 낮은 강연을 pop해준다.

 

from heapq import *
n=int(input())
a=[tuple(map(int,input().split())) for _ in range(n)]
q=[]
for w,d in sorted(a,key=lambda x:x[1]):
    heappush(q,w)
    if d<len(q):heappop(q)
print(sum(q))