본문 바로가기

카테고리 없음

[백준 1781번] 컵라면 (Python3)

import sys
input = sys.stdin.readline
from heapq import heappop,heappush

N = int(input())

ramen = [[] for i in range(N)]
for i in range(N):
  d,r = map(int,input().split())
  ramen[N-d].append(r)

result = 0
hq = []
for i in range(N):
  for r in ramen[i]:
    heappush(hq,-r)
  if hq:
    result -= heappop(hq)

print(result)

너무 간단한 우선순위 큐 활용 문제

데드라인이 가장 긴 문제부터 우선순위큐에 넣고 가장 컵라면을 많이 얻는 문제부터 풀면 된다.

 

뒤에서부터 세어야 한다는게 트릭이라면 트릭인데 그걸 감안해도 왜 골드2인지 모르겠는...