BOJ :: [2109] 순회강연

문제

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

2109번: 순회강연

 

문제 요약

순회강연 문제는 여러 대학에서 강연 제의를 받은 학자가 가장 많은 돈을 받을 수 있는 일정으로 강연을 하고자 한다. 강연 데드라인과 강연료가 주어지며 강연 데드라인 안에만 강연을 해주면 강연료를 받을 수 있다. 이때 학자가 가장 많이 받을 수 있는 강연료를 출력하는 문제이다. 기간 내에 가능한 강연을 선택할 수 있다는 것은 기간이 20일이라면, 1일부터 20일까지의 기간 중 아무 데나 강연을 진행하고 강연료를 받을 수 있다는 의미이다. 만약 4개의 대학에서 강연 기간이 1, 1, 2, 2, 강연료가 10, 10, 30, 30이라면, 1은 강연까지 당장 남은 기간이 하루밖에 없다는 의미이고, 2는 강연까지 남은 기간이 2일로 1일 차에 2일 강연, 2일 차에 또 2일 남은 강연을 진행하여 최대 강연료인 60만큼의 강연료를 받을 수 있다. 

 

문제 풀이

이 문제는 기간 내에 가능한 강연 중 최대 비용을 선택해야 하는 문제로, 강연을 할 수 있는 기간을 최대 기간으로 정하고 하루씩 줄여가며 현재 기간에 가능한 최대 비용의 강연을 선택하는 그리디 방법으로 해결할 수 있다. 강연이 가능한 날짜를 데드라인으로 잡고 주어진 데드라인 중 가장 긴 데드라인을 기준으로 하루씩 줄여가며 일정을 정한다. 아래 코드에서는 데드라인의 날짜가 많이 남아있는 순서로 저장하는 데드라인 큐와 강연이 가능한 경우 높은 강연료 순서대로 저장하는 강연료 큐까지 두 개의 큐를 사용한다. 그리고 데드라인을 하루씩 줄여가며 강연료 큐에서 해당 데드라인에 가능한 강연이 있다면 가장 강연료가 높은 강연을 일정에 추가하고, 결과를 더해 최대 강연료를 계산한다. 

 

코드

import sys
import heapq

input = sys.stdin.readline

n = int(input())

pq = []
rq = []

for i in range(n):
    p, d = map(int, input().split())
    heapq.heappush(pq, (-d, p))

deadline = 0
if len(pq) > 0:
    deadline = -pq[0][0]

result = 0
while deadline > 0:
    while pq:
        d, p = heapq.heappop(pq)
        if -d < deadline:
            heapq.heappush(pq, (d, p))
            break

        heapq.heappush(rq, -p)
    
    if len(rq) > 0:
        c = heapq.heappop(rq)
        result += c
    
    deadline -= 1

print(-result)

 

 

작성한 글에 잘못된 부분이나 문제가 있는 경우 댓글에 작성해 주시면 수정하도록 하겠습니다 . 질문도 환영합니다! :)