[python] 백준 - 1202 (보석 도둑)

골드2 문제이며, 제한 시간은 1초이다.

문제

해결 과정

처음에 이 문제를 딱 접했을 때, 보석의 가격을 기준으로 우선순위 큐를 사용해서 현재 탐색 중인 가방과 비교해서 가방의 용량보다는 무게가 가볍고, 가치는 큰 보석을 선택하려 했다. 실패한 과정은 우선순위 큐를 한 개만 사용하고, 조건문으로 나머지를 처리하려 했다. 정답으로 가는 방향은

1. 우선순위 큐(최소 힙)를 보석의 무게를 기준으로 넣는다.
2. 가방은 오름차순 정렬을 한다.
3. 현재 탐색 중인 가방의 용량보다 무게가 더 무거운 보석이 나오기 전까지 보석의 가격을 기준으로 하는 최대 힙에 넣는다.
4. 다 넣었으면 pop하여 맨 앞에 가격이 제일 높은 보석의 가격을 결과에 더해준다.
5. 다음 가방을 탐색하며 3~4번 과정을 반복한다.

풀이

import sys, heapq

input = sys.stdin.readline

n, k = map(int, input().split())
jewels = []
for _ in range(n):
    weight, price = map(int, input().split())
    heapq.heappush(jewels, (weight, price))

bags = sorted([int(input()) for _ in range(k)])
result = 0

available_jewels = []
for bag in bags:
    while jewels and jewels[0][0] <= bag:
        weight, price = heapq.heappop(jewels)
        heapq.heappush(available_jewels, -price)

    if available_jewels:
        result -= heapq.heappop(available_jewels)

print(result)

우선순위 큐를 사용하는 방법에 대해 더 고민하게 되는 문제였다.