[Python/파이썬] - 백준(BOJ) 1781번 : 컵라면

https://www.acmicpc.net/problem/1781

1781번: 컵라면

 

n+1개의 arr 배열을 생성하여 컵라면 개수를 arr[끝나는 시간]에 맞게 저장해준다.

끝나는 시간이 널널한 것은 나중에 처리해도 되기 때문에

끝나는 시간 최대값을 m으로 저장하고 arr m부터 1까지 역순으로 heappush후 heappop하여 최대값을 꺼낸다.

최대값을 꺼낸 후 answer를 증가시킨다.

 

import sys
from heapq import heappop, heappush
input = sys.stdin.readline
n = int(input())
arr = [[] for _ in range(n+1)]
m = 0
for _ in range(n):
    a, b = map(int,input().split())
    arr[a].append(b)
    m = max(m, a)

heap = []
answer = 0
for i in range(m, 0, -1):
    for x in arr[i]:
        heappush(heap, -x)
    if heap:
        answer -= heappop(heap)
print(answer)