[baekjoon] 백준 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만큼의 돈을 벌 수 있다.

알고리즘

- 강연의 수를 입력받는다.

- 페이와 날짜를 강연의 수만큼 반복하여 입력받아 리스트에 넣는다.

- 제일 빨리 강연하는 날부터 비교하기 위해 d 기준으로 오름차순 정렬한다.

- 페이와 날짜를 반복문을 통해 비교한다.

- 강연을 해야하는 날짜를 오름차순으로 정렬했기 때문에 제일 먼저 강연해야 하는 날짜부터 비교하게 된다.

- 강연을 해야 하는 날보다 이미 강연을 약속한 날(heap의 길이)이 더 크면 이미 강연한 날에서 제일 적게 페이를 주는 강연을 빼준다.

- 이미 강연을 약속한 날의 페이를 모두 더하여 출력한다.

코드

import sys
import heapq

n = int(sys.stdin.readline())
pd = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
# 제일 빨리 강연하는 날부터 비교하기 위해 d 기준으로 오름차순 정렬한다.
pd.sort(key=lambda x: x[1])
heap = []

for p, d in pd:
    # 제일 빨리 하는 강연에 페이를 heap 리스트에 푸시한다.
    heapq.heappush(heap, p)

    # heap 리스트에 길이가 강연을 해야하는 날짜보다 크면 모든 강연을 못하므로 제일 작은 페이를 팝한다.
    # 반대로 작거나 같을경우는 강연을 할 수 있는 날이 되는 것이다.
    if len(heap) > d:
        heapq.heappop(heap)

# 힙안에 들어있는 페이를 모두 더한다.
print(sum(heap))

github

junjange/CodingTest