[BOJ 1781, Python 3] 컵라면

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

1781번: 컵라면

 

풀이

순회 강연, 과제 문제와 과정은 똑같고 범위만 다릅니다.

이 문제에서는 N = 100,000이라서 x일 이내에 풀 수 있으면 반복문을 이용해 1~x일을 확인하여 매칭해주면 시간초과가 나옵니다.

그래서 데드라인을 기준으로 오름차순으로 정리하고, 반복문을 통해 우선순위 큐에 넣어주다가 우선순위 큐의 길이가 현재 보고 있는 과제의 데드라인보다 크면 가장 작은 값 하나를 빼주면 됩니다.

 

이게 왜 가능하냐면 데드라인을 오름차순으로 정렬했으니 데드라인이 x일인 문제는 1일~x일 아무때나 풀어도 상관 없기 때문입니다.

 

 

코드

from heapq import *
input = __import__('sys').stdin.readline
 
n = int(input())
arr = sorted([[*map(int, input().split())] for _ in range(n)])
q = []
for i in range(n):
    heappush(q, arr[i][1])
    if len(q) > arr[i][0]:
        heappop(q)
print(sum(q))