이번 문제는 그리디 알고리즘과 heapq를 이용하여 해결하였다. 그리디 문제는 생각을 다르게 해야되는 경우가 많아 많은 연습이 필요할 것 같다 ...

처음에는 단순하게 입력받은 데이터를 p의 내림차순, d의 오름차순으로 정렬 순위를 정하여 정렬한 후에, 현재 날짜를 세며 d가 현재 날짜보다 같거나 같을 경우 수행하도록 하였다. 그러나 이 코드는 다음과 같은 경우를 해결할 수 없다.

input: 3
	   10 1
       50 2
       100 2
output: 110
answer: 150

이를 해결하기 위해 많은 생각을 했지만 도저히 생각나지 않았다. 결국 최소힙을 사용한다는 힌트를 얻고 생각을 할 수 있었다.

우선 입력받은 데이터를 d의 오름차순으로 정렬하고, 이를 순회하며 최소힙에 데이터를 하나씩 넣는다. 이 과정에서 만약 최소힙의 길이가 현재 데이터의 d보다 클 경우, 그만큼의 강연을 수행할 수 없으므로 최소힙에서 heappop을 해준다. 이렇게 되면 해당하는 날에 대해서 가장 작은 p를 없앨 수 있게 되기 때문에 최댓값을 구할 수 있게 된다.

Code

import heapq
n = int(input())
suggest = sorted([list(map(int, input().split())) for _ in range(n)], key = lambda x:(x[1]))
answers = []
for i in range(n):
    heapq.heappush(answers, suggest[i])
    if len(answers) > suggest[i][1]:
        heapq.heappop(answers)
answer = 0
while answers:
    answer += answers.pop()[0]
print(answer)