[BOJ] 2109 순회강연 (Python3)

문제

한 저명한 학자에게 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  
7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

예제 출력 1  
185

코드

import heapq

n = int(input())
lecture = []

for i in range(n):
    p,d = map(int, input().split())
    lecture.append([p,d])

lecture.sort(key = lambda x : x[1])

total = []

for i in lecture:
    heapq.heappush(total, i[0])
    if len(total) > i[1] :
        heapq.heappop(total)
print(sum(total))

    

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10
185

문제풀이

기한이 지나지 않은 강의중 가장 돈을 많이 주는 강연순서대로 다녀야 최대로 많은 돈을 벌 수 있다. 따라서 먼저 0원보다는 1원이라도 버는게 더 총합액을 늘려주므로, 기한을 기준으로 오름차순 정렬해준다. 이후, 힙큐에 넣어가며 힙큐가 기한보다 많은 요소를 갖고있다면 heappop하여 가장 돈을 적게 버는 강연을 제거해주면 된다.