[백준 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값이 주어진다.

출력

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

풀이

최대로 돈을 벌기 위해서 데드라인인 d안에서 가장 많은 돈을 주는 강연을 가면 된다.

따라서 입력값을 데드라인을 기준으로 오름차순으로 정렬한다.

이후 반복문을 순회하면서 heapq 리스트에 값을 추가하고

리스트의 길이와 데드라인을 비교한다.

리스트의 길이가 데드라인보다 클 경우 데드라인을 넘긴 강연이 있는 것이기 때문에

pop을 이용하여 리스트 값 중 가장 작은 값을 제거한다.

반복문이 끝나고 리스트의 값을 모두 더하여 출력한다.

 

import sys
import heapq
n = int(sys.stdin.readline().rstrip("\n"))
nums = []
for _ in range(n):
    value, day = map(int, sys.stdin.readline().rstrip().split())
    nums.append([value, day])
nums = sorted(nums, key=lambda x:x[1])
sums = []
for num in nums:
    heapq.heappush(sums,num[0])
    if(len(sums) > num[1]):
        heapq.heappop(sums)
print(sum(sums))