[백준] 1781 컵라면 (파이썬)

문제링크: https://www.acmicpc.net/problem/1781

난이도 : GOLD II

문제해결

• 문제푸는데 1의 시간이 소모 되므로
• 데드라인별로 풀수 있는 문제는 1개이다.
• 즉 데드라인 >= 내가 푼 문제 을 만족 해야한다.
• 컵라면의 최대의 갯수을 구해야하므로 최소 힙을 사용하자.

import heapq
import sys

input = sys.stdin.readline

n = int(input())

arr = []

for _ in range(n):
    d, c = map(int, input().split())  # 데드라인,컵라면
    arr.append((d, c))

arr.sort(key=lambda x:x[0]) #데드라인 낮은 순 정렬

h = []

for dead,cup in arr:
  heapq.heappush(h,cup)
  if dead < len(h): #데드라인 보다 푼 문제가 많으므로 최소힙을 pop한다.
    heapq.heappop(h)
print(sum(h))