순회강연 #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값이 주어진다.

출력

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

예제 입력 1 복사

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

예제 출력 1 복사

185

출처

ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2003 D번

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

 

---

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

'''
1. 아이디어 :
    1)  그리디 문제다. 해당 날짜까지 제일 가격이 낮은 가격을 제외한다.
        예를 들어, 2일까지는 2개의 강의만 할 수 있으므로, 제일 가격이 높은 2개를 제외하고 나머지는 없앤다.
        또, 3일까지는 3개의 강의만 할 수 있으므로, 제일 가격이 높은 3개를 제외하고 나머지는 없앤다.
        Heap을 이용하여 배열의 길이(강의 수)가 해당 일수보다 높으면, 가장 작은 값 제외.
        마지막 heap 안에 남아있는 값들을 모두 더한다.
2. 시간복잡도 :
    1) O(nlogn) + O(nlogn) = O(nlogn)
        정렬 + n * (Heappush, HeapPop)
3. 자료구조 :
    1) Heap
'''

import sys
import heapq

input = sys.stdin.readline
lectures = sorted([[pay, day] for pay, day in [map(int, input().split()) for x in range(int(input()))]],
                  key=lambda x: x[1])
min_heap = []
for pay, day in lectures:
    heapq.heappush(min_heap, pay)
    if day < len(min_heap):
        heapq.heappop(min_heap)
print(sum(min_heap))