백준 온라인 저지, 그리디 / 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

힌트

W3sicHJvYmxlbV9pZCI6IjIxMDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMWNcdWQ2OGNcdWFjMTVcdWM1ZjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU1YyBcdWM4MDBcdWJhODVcdWQ1NWMgXHVkNTU5XHVjNzkwXHVjNWQwXHVhYzhjIG4oMCAmbGU7IG4gJmxlOyAxMCwwMDApXHVhYzFjXHVjNzU4IFx1YjMwMFx1ZDU1OVx1YzVkMFx1YzExYyBcdWFjMTVcdWM1ZjAgXHVjNjk0XHVjY2FkXHVjNzQ0IFx1ZDU3NCBcdWM2NTRcdWIyZTQuIFx1YWMwMSBcdWIzMDBcdWQ1NTlcdWM1ZDBcdWMxMWNcdWIyOTQgZCgxICZsZTsgZCAmbGU7IDEwLDAwMClcdWM3N2MgXHVjNTQ4XHVjNWQwIFx1YzY0MFx1YzExYyBcdWFjMTVcdWM1ZjBcdWM3NDQgXHVkNTc0IFx1YzhmY1x1YmE3NCBwKDEgJmxlOyBwICZsZTsgMTAsMDAwKVx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWFjMTVcdWM1ZjBcdWI4Y2NcdWI5N2MgXHVjOWMwXHViZDg4XHVkNTU4XHVhY2EwXHViMmU0XHVhY2UwIFx1YzU0Y1x1YjgyNFx1YzY1NFx1YjJlNC4gXHVhYzAxIFx1YjMwMFx1ZDU1OVx1YzVkMFx1YzExYyBcdWM4MWNcdWMyZGNcdWQ1NThcdWIyOTQgZFx1YzY0MCBwXHVhYzEyXHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5N2MgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1ZDU1OVx1Yzc5MFx1YjI5NCBcdWM3NzRcdWI5N2MgXHViYzE0XHVkMGQ1XHVjNzNjXHViODVjLCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YjNjOFx1Yzc0NCBcdWJjOGMgXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCBcdWMyMWNcdWQ2OGNcdWFjMTVcdWM1ZjBcdWM3NDQgXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVhYzE1XHVjNWYwXHVjNzU4IFx1ZDJiOVx1YzEzMVx1YzBjMSwgXHVjNzc0IFx1ZDU1OVx1Yzc5MFx1YjI5NCBcdWQ1NThcdWI4ZThcdWM1ZDAgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWFjZjNcdWM1ZDBcdWMxMWNcdWI5Y2MgXHVhYzE1XHVjNWYwXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YjEyNCBcdWIzMDBcdWQ1NTlcdWM1ZDBcdWMxMWMgXHVjODFjXHVjMmRjXHVkNTVjIHBcdWFjMTJcdWM3NzQgXHVhYzAxXHVhYzAxIDUwLCAxMCwgMjAsIDMwXHVjNzc0XHVhY2UwLCBkXHVhYzEyXHVjNzc0IFx1Y2MyOFx1Yjg0MFx1Yjg1YyAyLCAxLCAyLCAxIFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1Yzc3NFx1YjdmNCBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVjY2FiXHVjOWY4IFx1YjBhMFx1YzVkMCA0XHViYzg4IFx1YjMwMFx1ZDU1OVx1YzVkMFx1YzExYyBcdWFjMTVcdWM1ZjBcdWM3NDQgXHVkNTU4XHVhY2UwLCBcdWI0NThcdWM5ZjggXHViMGEwXHVjNWQwIDFcdWJjODggXHViMzAwXHVkNTU5XHVjNWQwXHVjMTFjIFx1YWMxNVx1YzVmMFx1Yzc0NCBcdWQ1NThcdWJhNzQgODBcdWI5Y2NcdWQwN2NcdWM3NTggXHViM2M4XHVjNzQ0IFx1YmM4YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViMzAwXHVkNTU5XHVjNWQwXHVjMTFjIFx1YzgxY1x1YzJkY1x1ZDU1YyBwXHVhYzEyXHVhY2ZjIGRcdWFjMTJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHViMzAwXHViODVjIFx1YmM4YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjNjOFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjEwOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN1cGVybWFya2V0IiwiZGVzY3JpcHRpb24iOiI8cD5BIHN1cGVybWFya2V0IGhhcyBhIHNldCBQcm9kIG9mIHByb2R1Y3RzIG9uIHNhbGUuIEl0IGVhcm5zIGEgcHJvZml0IHA8c3ViPng8XC9zdWI+IGZvciBlYWNoIHByb2R1Y3QgeCZpc2luO1Byb2Qgc29sZCBieSBhIGRlYWRsaW5lIGQ8c3ViPng8XC9zdWI+IHRoYXQgaXMgbWVhc3VyZWQgYXMgYW4gaW50ZWdyYWwgbnVtYmVyIG9mIHRpbWUgdW5pdHMgc3RhcnRpbmcgZnJvbSB0aGUgbW9tZW50IHRoZSBzYWxlIGJlZ2lucy4gRWFjaCBwcm9kdWN0IHRha2VzIHByZWNpc2VseSBvbmUgdW5pdCBvZiB0aW1lIGZvciBiZWluZyBzb2xkLiBBIHNlbGxpbmcgc2NoZWR1bGUgaXMgYW4gb3JkZXJlZCBzdWJzZXQgb2YgcHJvZHVjdHMgU2VsbCZzdWJlO1Byb2Qgc3VjaCB0aGF0IHRoZSBzZWxsaW5nIG9mIGVhY2ggcHJvZHVjdCB4JmlzaW47U2VsbCwgYWNjb3JkaW5nIHRvIHRoZSBvcmRlcmluZyBvZiBTZWxsLCBjb21wbGV0ZXMgYmVmb3JlIHRoZSBkZWFkbGluZSBkPHN1Yj54PFwvc3ViPiBvciBqdXN0IHdoZW4gZDxzdWI+eDxcL3N1Yj4gZXhwaXJlcy4gVGhlIHByb2ZpdCBvZiB0aGUgc2VsbGluZyBzY2hlZHVsZSBpcyBQcm9maXQoU2VsbCk9JnN1bTs8c3ViPngmaXNpbjtTZWxsPFwvc3ViPiBwPHN1Yj54PFwvc3ViPiAuIEFuIG9wdGltYWwgc2VsbGluZyBzY2hlZHVsZSBpcyBhIHNjaGVkdWxlIHdpdGggYSBtYXhpbXVtIHByb2ZpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGNvbnNpZGVyIHRoZSBwcm9kdWN0cyBQcm9kPXthLGIsYyxkfSB3aXRoIChwPHN1Yj5hPFwvc3ViPixkPHN1Yj5hPFwvc3ViPik9KDUwLDIpLCAocDxzdWI+YjxcL3N1Yj4sZDxzdWI+YjxcL3N1Yj4pPSgxMCwxKSwgKHA8c3ViPmM8XC9zdWI+LGQ8c3ViPmM8XC9zdWI+KT0oMjAsMiksIGFuZCAocDxzdWI+ZDxcL3N1Yj4sZDxzdWI+ZDxcL3N1Yj4pPSgzMCwxKS4gVGhlIHBvc3NpYmxlIHNlbGxpbmcgc2NoZWR1bGVzIGFyZSBsaXN0ZWQgaW4gdGFibGUgMS4gRm9yIGluc3RhbmNlLCB0aGUgc2NoZWR1bGUgU2VsbD17ZCxhfSBzaG93cyB0aGF0IHRoZSBzZWxsaW5nIG9mIHByb2R1Y3QgZCBzdGFydHMgYXQgdGltZSAwIGFuZCBlbmRzIGF0IHRpbWUgMSwgd2hpbGUgdGhlIHNlbGxpbmcgb2YgcHJvZHVjdCBhIHN0YXJ0cyBhdCB0aW1lIDEgYW5kIGVuZHMgYXQgdGltZSAyLiBFYWNoIG9mIHRoZXNlIHByb2R1Y3RzIGlzIHNvbGQgYnkgaXRzIGRlYWRsaW5lLiBTZWxsIGlzIHRoZSBvcHRpbWFsIHNjaGVkdWxlIGFuZCBpdHMgcHJvZml0IGlzIDgwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCByZWFkcyBzZXRzIG9mIHByb2R1Y3RzIGZyb20gYW4gaW5wdXQgdGV4dCBmaWxlIGFuZCBjb21wdXRlcyB0aGUgcHJvZml0IG9mIGFuIG9wdGltYWwgc2VsbGluZyBzY2hlZHVsZSBmb3IgZWFjaCBzZXQgb2YgcHJvZHVjdHMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5BIHNldCBvZiBwcm9kdWN0cyBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIDAmbGU7biZsZTsxMDAwMCwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBwcm9kdWN0cyBpbiB0aGUgc2V0LCBhbmQgY29udGludWVzIHdpdGggbiBwYWlycyBwPHN1Yj5pPFwvc3ViPiBkPHN1Yj5pPFwvc3ViPiBvZiBpbnRlZ2VycywgMSZsZTtwPHN1Yj5pPFwvc3ViPiZsZTsxMDAwMCBhbmQgMSZsZTtkPHN1Yj5pPFwvc3ViPiZsZTsxMDAwMCwgdGhhdCBkZXNpZ25hdGUgdGhlIHByb2ZpdCBhbmQgdGhlIHNlbGxpbmcgZGVhZGxpbmUgb2YgdGhlIGktdGggcHJvZHVjdC4gV2hpdGUgc3BhY2VzIGNhbiBvY2N1ciBmcmVlbHkgaW4gaW5wdXQuIElucHV0IGRhdGEgdGVybWluYXRlIHdpdGggYW4gZW5kIG9mIGZpbGUgYW5kIGFyZSBndWFyYW50ZWVkIGNvcnJlY3QuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggc2V0IG9mIHByb2R1Y3RzLCB0aGUgcHJvZ3JhbSBwcmludHMgb24gdGhlIHN0YW5kYXJkIG91dHB1dCB0aGUgcHJvZml0IG9mIGFuIG9wdGltYWwgc2VsbGluZyBzY2hlZHVsZSBmb3IgdGhlIHNldC4gRWFjaCByZXN1bHQgaXMgcHJpbnRlZCBmcm9tIHRoZSBiZWdpbm5pbmcgb2YgYSBzZXBhcmF0ZSBsaW5lLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

접근 방법

- 0. 주어진 강연정보를 각 대학별 날짜를 기준으로 오름차순 정렬하고, 강연 페이를 기준으로 하는 최소힙을 초기화한다.
- 1. 강연정보를 하나씩 탐색하며 최소힙의 길이보다 현재 탐색중인 날짜가 크다면 이를 최소힙에 삽인한다.
- 2. 만약 최소힙의 길이가 현재 탐색중인 날짜보다 같다면 최소힙의 0번째 인덱스와 현재 탐색중인 강연의 급여를 비교해 더 큰 값을 삽입하고 작은 값은 최소힙에 넣지 않거나 뺀다.
- 모든 탐색이 끝난 뒤, 최소힙을 모두 합해 값을 출력한다.

코드

# https://www.acmicpc.net/problem/2109
# 접근 방법
# 0. 주어진 강연정보를 각 대학별 날짜를 기준으로 오름차순 정렬하고, 강연 페이를 기준으로 하는 최소힙을 초기화한다.
# 1. 강연정보를 하나씩 탐색하며 최소힙의 길이보다 현재 탐색중인 날짜가 크다면 이를 최소힙에 삽인한다.
# 2. 만약 최소힙의 길이가 현재 탐색중인 날짜보다 같다면 최소힙의 0번째 인덱스와 현재 탐색중인 강연의 급여를 비교해 더 큰 값을 삽입하고 작은 값은 최소힙에 넣지 않거나 뺀다.
# 모든 탐색이 끝난 뒤, 최소힙을 모두 합해 값을 출력한다.
import sys, heapq
input = sys.stdin.readline
n = int(input())
array = [list(map(int, input().split())) for _ in range(n)]
array.sort(key=lambda x: x[1])
min_heap = []
for pay, day in array:
    if day > len(min_heap):
        heapq.heappush(min_heap, pay)
    else:
        if min_heap[0] < pay:
            heapq.heappop(min_heap)
            heapq.heappush(min_heap, pay)
total_pay = sum(min_heap)
print(total_pay)