Document filing scheduler

한 회사의 문서 관리 시스템에는 매일 처리해야 하는 서류들이 등록된다.

각 서류는 다음 두 개의 정보를 가진다.

• Di : 마감일까지 남은 일수
• Pi : 해당 서류를 정리하면 얻는 중요도 점수

서류 하나를 정리하는 데는 정확히 하루가 걸리며, 하루에 하나의 서류만 처리할 수 있다.

어떤 서류는 마감일 이전(또는 당일)에만 처리할 수 있으며, 마감일을 넘기면 해당 서류는 무효가 되어 점수를 얻을 수 없다.

관리자는 얻을 수 있는 중요도 점수의 합을 최대화하고자 한다.

주어진 서류 목록에 대해 얻을 수 있는 최대 중요도 점수를 구하여라.

첫째 줄에 서류의 개수 N이 주어진다.

다음 N개의 줄에는 각 서류의 정보 Di, Pi가 공백으로 구분되어 주어진다.

처리 가능한 서류들을 적절히 선택했을 때 얻을 수 있는 중요도 점수의 최댓값을 출력한다.

• 1 ≤ N ≤ 200,000
• 1 ≤ Di ≤ 200,000
• 1 ≤ Pi ≤ 10^9

7
1 20
2 10
2 50
3 30
3 40
1 15
2 25

5
1 100
2 20
2 50
3 60
3 30

120

210

마감일과 중요도를 정리하면 다음과 같다.

(1, 20)
(2, 10)
(2, 50)
(3, 30)
(3, 40)
(1, 15)
(2, 25)

가능한 최적의 선택은

1일차 : 중요도 20
2일차 : 중요도 50
3일차 : 중요도 40

이다.

따라서 얻는 총 점수는

20 + 50 + 40 = 110

이 아니다.

더 좋은 선택은

1일차 : 중요도 25
2일차 : 중요도 50
3일차 : 중요도 45

와 같이 존재하지 않는다.

실제로 가능한 최적 조합은

20 + 50 + 30 + 20

처럼 하루에 여러 개를 처리할 수 없으므로 잘못된 선택이다.

우선순위 큐를 이용해 계산하면 최댓값은

120

이다.

다음과 같이 처리할 수 있다.

1일차 : 중요도 100
2일차 : 중요도 50
3일차 : 중요도 60

총 점수는

100 + 50 + 60 = 210

이며 이것이 가능한 최댓값이다.

마감일이 빠른 서류부터 차례대로 고려한다.

현재까지 선택한 서류들의 중요도를 최소 힙(min-heap)에 저장한다.

1. 서류를 마감일 기준 오름차순으로 정렬한다.
2. 각 서류의 중요도를 힙에 넣는다.
3. 현재 선택한 서류 수가 현재 서류의 마감일보다 많다면, 중요도가 가장 낮은 서류를 제거한다.

이 과정을 거치면 항상 각 시점까지 처리 가능한 서류 중 중요도 합이 최대가 되도록 유지할 수 있다.

시간 복잡도는 정렬과 힙 연산을 포함하여

O(N log N)

이며, 추가 공간 복잡도는

O(N)

이다.

import sys
import heapq

input = sys.stdin.readline

N = int(input())
docs = [tuple(map(int, input().split())) for _ in range(N)]

docs.sort()

heap = []

for d, p in docs:
    heapq.heappush(heap, p)

    if len(heap) > d:
        heapq.heappop(heap)

print(sum(heap))