[알고리즘] BOJ 2109 순회강연

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

---

📍 출력

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

---

📍 풀이

✍ 코드

# 2109 순회 강연 < 골드 3 >
import heapq
from sys import stdin
lst, heap = [], [] # [pay, day] 배열, heap 배열
income = 0 # 총 수입
N = int(stdin.readline())
for _ in range(N):
  p, d = map(int,stdin.readline().split())
  lst.append([d,p])
lst.sort() # 일자 기준 오름차순 정렬
for i in range(N):
  [day, pay] = lst[i]
  heapq.heappush(heap, [pay,day]) # 힙에 현재 일정 추가
  if day < len(heap): # 현재 날짜보다 많은 일정이 있다면
    heapq.heappop(heap) # 제일 작은 일정 제거
for h in heap:
  income += h[0]
print(income)