백준 2109
최대로 벌 수 있는 돈 구하기.
- 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다.
- 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다.
- 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.
- 첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.
- 첫째 줄에 최대로 벌 수 있는 돈을 출력한다.
입출력
| 입력 | 출력 |
|---|---|
| 7 20 1 2 1 10 3 100 2 8 2 5 20 50 10 | 185 |
접근 방식
: 기한을 key로 비용을 value로 하는 딕셔너리를 만들어 각 기한에 대한 비용을 내림차순 정렬한다.
딕셔너리의 각 기한에 대해 첫번째 비용을 더해 출력한다.
알게된 점
3
1 1
10 2
10 2
일 때, 답은 11이 아닌 20이다. 2일 안에 오면 되기 때문에 1일차에 +10, 2일차에 +10
이러한 경우를 간과했다.
- 기한 기준으로 그래프를 오름차순 정렬
- 힙에 기한에 대한 가격을 넣고, 힙의 길이가 기한보다 크면 못가는 강연이 있는 것이므로 heappop으로 가장 적은 가격을 제거.(최소힙이기 때문)
코드
import sys
import heapq
n = int(sys.stdin.readline())
graph = []
for _ in range(n):
p, d = map(int, sys.stdin.readline().split())
graph.append((d, p))
graph.sort()
q = []
for d, p in graph:
heapq.heappush(q, p)
if len(q) > d:
heapq.heappop(q)
print(sum(q))