[BOJ 2109] 순회강연 (파이썬)

 

안녕하세요. 오늘은 백준에 있는 2109번 순회강연 문제를 풀어보려고 합니다.

문제의 출처는 아래와 같습니다.

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

 

1. 문제

한 저명한 학자에게 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만큼의 돈을 벌 수 있다.

 

2. 입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

 

3. 출력

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

 

4. 예제 입력

7

20 1

2 1

10 3

100 2

8 2

5 20

50 10

 

5. 예제 출력

185

 

6. 문제 풀이

heap을 잘 활용하면 문제를 쉽게 풀 수 있습니다.

우선 main문에서는 p,d를 입력 받고 p,d를 d,p 순서의 튜플로 리스트에 저장을 해줍니다.

그리고 나중에 d의 순서대로 대학을 확인하기 위하여 리스트를 정렬합니다.

 

heap에 값을 저장할 때는 대학에서 주기로한 강연료를 저장해주고 만약 heap의 길이가 univ[0], 즉 날짜의 값보다 크다면 현재 heap에 있는 가장 작은 값을 pop해줍니다.

이렇게 함으로서 날짜 안에 갈 수 있는 대학들 중에서 강연료를 제일 많이 주는 대학들만 heap에 남게 됩니다.

마지막으로 heap에 있는 값들을 모두 더해서 return하면 정답을 올바르게 return할 수 있습니다.

 

6. 전체 코드

import sys
import heapq

def lec_tour(univ_list):
    
    heap = []

    for univ in univ_list:
        heapq.heappush(heap, univ[1])
        # delete the univ which gives the lowest payment
        if len(heap) > univ[0]:
            heapq.heappop(heap)

    return sum(heap)

if __name__ == '__main__':

    n = int(sys.stdin.readline())
    univ_list = []

    for _ in range(n):
        p, d = map(int, sys.stdin.readline().split())
        univ_list.append((d,p))
        
    univ_list.sort()

    print(lec_tour(univ_list))