1 minute read

2109번 : 순회강연

문제 링크

https://www.acmicpc.net/problem/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값이 주어진다.

출력

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

문제 풀이

이와 비슷한 문제를 이전에 풀었어서 어렵지 않게 해결했다.

from heapq import heappush, heappop

# 대학교 수 입력
N = int(input())
arr = []
temp = []
count = 0 

# 각 대학교의 p(강연료), d(기한)을 입력받음
# d 내림차순, p 내림차순으로 입력받음
for i in range(N) :
    p, d = map(int, input().split())
    heappush(arr, (-d, -p))

# 대학교 수가 1이상인 경우에만 아래 코드를 실행
if arr : 
    
    # 맨처음 d값부터 1일까지 반복
    for i in range(-arr[0][0], 0, -1) : 
    
        # arr 남은 항목이 있고, temp에 남은 항목이 없고, arr 중 가장 큰 기한보다 현재 일수가 크면 continue
        if arr and len(temp) == 0 and -arr[0][0] < i : continue 
    
        # 현재 일자보다 크거나 같은 d가 나오면 temp 배열에 push
        while arr and -arr[0][0] >= i: 
            d, p = heappop(arr)
            heappush(temp, p)

        # 끝나면 temp에서 pop한(강연료가 가장 높은) 값을 count에 더하기
        if temp : 
            count -= heappop(temp)
        
# 마지막에 count한 p값을 출력
print(count)

Comments

You May Also Enjoy