(Python/파이썬) - 백준(BOJ) 2109번 : 순회강연

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

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만큼의 돈을 벌 수 있다.

 

 

 

---

• 풀이 :

그리디, 우선순위 큐 문제였습니다.

 

풀이입니다.

 

1. 입력받은 p와 d를 리스트에 넣고 d 값을 기준으로 오름차순 정렬합니다. 데드라인이 빠른 강연부터 체크하기 위함입니다.

 

2. 데드라인이 낮은 강의부터 갈 수 있는 강의인지 확인합니다. 이 때, 갈 수 없는 강의(데드라인을 넘긴 강의)가 발생한 경우 현재까지 탐색한 갈 수 있는 모든 강의들 중 가장 코스트가 적은 강의를 뺍니다. 이 작업을 위해 heap을 사용합니다.

heap은 삽입, 삭제의 시간복잡도가 O(logN)입니다. 매번 가장 코스트가 적은 강의를 찾기 위해 sort를 진행한다면 O(NlogN)으로 훨씬 많은 시간자원을 소모하게 됩니다.

 

 

 

 

 

---

• 소스코드 : 

import sys
import heapq as hq
input = sys.stdin.readline


N = int(input())
uni = []
answer = []
curr_uni = 0
for _ in range(N):
    p,d = map(int,input().split())
    uni.append([p,d])
for p,d in sorted(uni, key=lambda x : x[1]): # 강연 데드라인을 기준, 오름차순 정렬
    hq.heappush(answer,p)
    curr_uni += 1 # 갈 수 있는 강연의 후보 개수 증가
    if curr_uni > d: # 갈 수 있는 강연의 후보 개수가 데드라인을 넘긴 경우
        hq.heappop(answer) # 가장 돈을 적게 주는 강연을 뺌
        curr_uni -= 1 
print(sum(answer))