[BOJ] 1781 - 컵라면 (Python)

 

 

아이디어

 

데드라인 오름차순으로 정렬 후 차례로 우선순위 큐에 추가해 컵라면을 많이 받을 수 있는 문제만 남긴다.

 

 

풀이

 

데드라인과 컵라면 수를 리스트 homework에 입력 받은 후 함수 solve를 호출한다.

함수 solve에서는 homework를 데드라인 오름차순으로 정렬한 후, for문으로 차례로 돈다.

데드라인이 우선순위 큐의 크기 cnt보다 크면 우선순위 큐 queue에 추가하고, 결과값을 컵라면 수만큼 증가시킨다.

그렇지 않다면 컵라면이 큐의 최솟값보다 클 때 최솟값 대신 현재 값을 큐에 넣고 결과값에 반영한다.

 

import sys, heapq

input = sys.stdin.readline

def solve():
    res = cnt = 0
    homework.sort(key=lambda x: x[0])
    for d, r in homework:
        if d > cnt:
            heapq.heappush(queue, r)
            cnt += 1
            res += r
        elif queue[0] < r:
            res -= heapq.heappop(queue)
            heapq.heappush(queue, r)
            res += r
    return res

N = int(input())
queue, homework = [], []
for _ in range(N):
    d, r = map(int, input().split())
    homework.append((d, r))
print(solve())

 

 

전에 풀었던 10775번 공항처럼 유니온 파인드로 풀려고 했더니 PyPy3는 통과되었지만 Python 3로는 시간 초과가 났다.

# 더 느린 코드(PyPy3), Python 3 기준 시간 초과
import sys, heapq

input = sys.stdin.readline

N = int(input())
queue = []
group = [i for i in range(N+1)]
for _ in range(N):
    d, r = map(int, input().split())
    heapq.heappush(queue, (-r, -d))
res = 0
while queue:
    r, d = heapq.heappop(queue)
    idx = -d
    while group[idx] != idx:
        idx = group[idx]
    if group[idx] == 0:
        continue
    group[idx] = group[idx-1]
    group[-d] = group[idx]
    res -= r
print(res)