이번 문제는 그리디 알고리즘을 통해 해결하였다. 주어진 데이터를 데드라인을 기준으로 오름차순 정렬한 후에, 이 리스트를 순회하며 최소힙에 (컵라면 수, 데드라인) 형태로 삽입해준다. 삽입한 후에 최소힙의 길이와 현재 데이터의 데드라인과 비교하여, 최소힙의 길이가 더 길 경우에 최소힙을 heappop해준다. 이 과정이 끝나면 최소힙에는 정답으로 취해야하는 데이터만 들어가게 된다. 쉽게 생각하면 최소힙에 전체 데이터를 넣으며 그때 그때 컵라면 수가 더 적은 것을 빼는 것이다.

Code

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