1781 : 컵라면

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

1781번: 컵라면

 

문제의 알고리즘 분류에 '우선순위 큐'가 나와있길래.. 시키는 대로 우선순위 큐를 사용해서 풀어보았다 !

 

우선순위 큐는 선입선출(FIFO) 특징을 가진 일반적인 큐와는 달리
데이터 추가 순서와는 상관 없이,  제거될 때는 가장 작은 값을 제거한다는 특징이 있다.
즉, 내부적으로 정렬이 된다는 뜻이고 파이썬에서는 heapq 모듈을 통해 구현된다.

 

우선순위 큐를 사용하면 문제가 아주 간단하게 풀린다 !

 

우선, 데드라인을 기준으로 (데드라인, 컵라면 수)를 정렬한다.

그리고 큐에 컵라면 수를 넣어주면서 데드라인과 큐의 길이를 비교한다.

만약 데드라인보다 큐의 길이가 더 크다면, 큐에 있는 컵라면 수에서 가장 작은 값을 제거하면 된다.

 

이 과정을 반복하고, 마지막은 큐에 있는 값들을 모두 더해 출력한다.

 

import sys
import heapq

n = int(sys.stdin.readline())

dr_input = []
q = []

for _ in range(n):
    dline, rnum = map(int, input().split())
    dr_input.append((dline, rnum))

dr_input.sort()

for dr in dr_input:
    heapq.heappush(q, dr[1])
    if dr[0] < len(q):
        heapq.heappop(q)


print(sum(q))

근데 Python3으로 하면 시간초과가 떠서 일단 PyPy3으로 했다....