(Python) 백준 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만큼의 돈을 벌 수 있다.
상세정보

• 우선순위큐로 풀 수 있는 그리디 문제로, '가장 강연료가 큰 강의를 우선해서 선택한다' 라는 그리디적 해결법으로 접근할 수 있다.
• 페이와 데이 순서로 주어지는데, 정렬을 위해서 데이와 페이 순서로 저장하였다. 다만 풀고나서 보니 굳이 데이와 페이 순서로 저장하지 않아도 람다 함수를 이용해서 데이를 기준으로 정렬해도 되었을 듯 싶다.
• 세미나 정보를 순회하면서 페이를 큐에 집어넣고, 만약 현재 데이보다 들어있는 세미나의 수가 더 많다면 가장 페이가 적은 강의를 힙큐를 통해 빼낸다.

from sys import stdin; input=stdin.readline
import heapq

N = int(input())

# P와 D가 주어지는데, D순으로 정렬할 거니까 순서 바꿔서 넣어주기
seminar = []
for _ in range(N):
    p, d = map(int,input().split())
    seminar.append((d,p))

seminar.sort() # 날짜순으로 정렬. 생각해보면 key=lambda로 정렬해도 상관없었을듯
que = []

for day, pay in seminar: # seminar 돌면서 날짜와 페이 확인
    heapq.heappush(que, pay) # 일단 큐에 집어넣기
    if day < len(que): # 만약 날짜보다 들어있는 세미나의 양이 많다면
        heapq.heappop(que) # 제일 페이가 낮은 세미나 뽑아내기

print(sum(que))