문제
한 저명한 학자에게 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값이 주어진다.
출력
첫째 줄에 최대로 벌 수 있는 돈을 출력한다.
예제 입력
7
20 1
2 1
10 3
100 2
8 2
5 20
50 10
예제 출력
185
풀이
어떻게 풀어야 하는지 감이 안왔던 문제,,
day 순으로 정렬해서 각 day마다 최대값을 뽑는 방법도 아니었고,
pay 순으로 정렬해서 각 day에 매칭되는 최댓값으로 기록해서 합을 구하는 방법도 아니었다.
핵심은 어떠한 일수까지는 해당 일수까지의 가능한 최대로 돈을 벌 수 있는 강연 순회 계획이 들어가야 한다는 것이다. 이걸 생각하면 아래와 같이 문제를 풀어갈 수 있다.
(day, pay) 튜플 배열이 [(1,2),(1,20),(2,8),(2,100),(3,10),(10,50),(20,5)]가 있다고 할 때,
1일까지 최대의 강연 순서는 (1,2), (1,20) 중에 (1,20)이 들어가야 한다. 그러면 2가 처음에 최대 수익으로 됐다가 20을 보고 20이 1일까지의 최대수익이 된다.
그럼 크기가 1인 공간에 20이라는 수익이 관리된다.20
그리고 2일까지는 가능한 경우의 수가 (2,8), (2,100)이 추가 된다. 이 경우에는 20에다가 8이 추가되고, 여기서 100이 추가되려고 하니 2일까지는 강연을 2개만 돌 수 있기때문에 8이 빠져야 최대가 된다. 따라서 8을 제외한 20, 100이 2일까지의 최대값이 된다.
그러면 이렇게 비용이 작은 순으로 쉽게 빼서, 해당 일수까지의 최대 강연 수익을 유지하기 위해서는 우선 순위 큐를 사용하는 것을 생각할 수 있다. 그리고 현재까지의 일수만큼의 길이를 가져야 해당 일수까지의 가능한 최댓 수익의 공연 순회 정보들을 관리할 수 있다.
import sys
import heapq
input = sys.stdin.readline
n = int(input())
arr = []
for _ in range(n):
pay, day = map(int, input().split())
arr.append((day,pay))
arr.sort(key=lambda x: x[0])
hq = []
for t in arr:
day = t[0]
pay = t[1]
# 힙큐에 넣은 후에
heapq.heappush(hq, pay)
if len(hq) > day:
heapq.heappop(hq)
print(sum(hq))