[Python] 백준 #2109 - 순회강연

문제

---

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

2109번: 순회강연

 

 

 

풀이

---

import sys
import heapq
n = int(input())
money = 0
arr = []
for _ in range(n):
    tmp = list(map(int,sys.stdin.readline().strip().split()))
    arr.append([tmp[0],tmp[1]])

arr = sorted(arr,key=lambda x: (x[1])) # 데드라인 오름차순

queue = []

for pay,day in arr:
    heapq.heappush(queue,pay)

    if day < len(queue): # 날짜보다 queue의 길이가 더 크면 
        heapq.heappop(queue) # 최소금액 pop

print(sum(queue))

 

우선순위 큐를 사용해주었다.

 

먼저 데드라인으로 오름차순을 해준다.

 

그 다음, 우선순위 큐에 하나씩 넣어준다.

이때 날짜보다 큐의 길이가 더 길다면 데드라인을 넘은 강의가 있는 것이기 때문에 최소금액을 pop해준다.