[우선순위큐,정렬] 백준-2109 순회강연 골드3 (Python)

백준-2109 : 순회강연

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

2109번: 순회강연

 

풀이

• 입력 받은 정보를 날짜 순으로 정렬을 한다.
• 정렬한 데이터를 꺼내면서 우선순위 큐에 넣으며 우선순위 큐의 크기가 날짜보다 클경우 가장 작은 비용의 값을 꺼낸다.

 

코드 (python)

import sys
import heapq

def input():
    return sys.stdin.readline().rstrip()


n = int(input()) 

infoList = [list(map(int, input().split(" "))) for _ in range(n)]

#날짜 순으로 정렬
infoList.sort(key=lambda x : x[1])

pq=[]

for pay, day in infoList:
    heapq.heappush(pq,pay)
    # 강연일 보다 더 크다면 가장 작은값 제거
    if day < len(pq):
        heapq.heappop(pq)

print(sum(pq))