#292 백준 파이썬 [1202] 보석 도둑 - 우선 순위 큐

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

 

SOLUTION

우선 순위 큐를 구현한 최대 최소힙을 통해 풀이하였다. 이를 모른다면 공부를 먼저 하고오길 추천한다.

현재 가장 작은 무게를 수용할 수 있는 가방(=capacity) 이하의 모든 보석(capable_gem) 중 가장 값이 큰 것을 뽑아내고 이를 가방이 끝날 때 까지 반복하는 것이 목표다.

 

다음과 같은 알고리즘을 따른다.

1) Bag의 최솟값을 heappop 해준다. 해당 Bag은 현재의 capacity 즉, 수용량이 된다.

2) 수용량 이하 무게의 모든 보석 Gem을 capable_gem에 무게를 제외한 값만 heappush하여 넣어준다.

3) capacity이하의 모든 무게의 보석을 꺼냈으면 capable_gem(최대 힙)중 가장 큰 값을 heappop하여 꺼낸 뒤 bag에 넣어준다(total_value에 추가한다).

4) beg이 남았지만 gem이 없을 경우(:모든 gem이 capable_gem일 경우) capable_gem에서 heappop하여 현재 bag에 차례대로 넣어준다.

5) 1~4를 반복한 뒤 bag이 더 이상 없거나, gem과 capable_Gem 모두가 비었으면 while문을 끝낸다.

PYTHON CODE

import heapq
import sys

N, K = map(int, input().split())
gem = []
for _ in range(N):
    weight, value = map(int, sys.stdin.readline().split())
    heapq.heappush(gem, [weight, value])

bag = []    
for _ in range(K):
    capacity = int(sys.stdin.readline())
    heapq.heappush(bag, capacity)

total_value = 0 #답이 될 숫자
capable_gem = [] #현재 bag의 capacity보다 작은 모든 보석들

for _ in range(K):
    capacity = heapq.heappop(bag) # Bag의 최솟값을 heappop 해준다. 해당 Bag은 현재의 capacity 즉, 수용량이 된다
    
    while gem and capacity >= gem[0][0]: #현재 bag의 capacity보다 이하인 모든 보석에 관하여
        [weight, value] = heapq.heappop(gem) #최소 무게부터 차례대로 꺼낸다
        heapq.heappush(capable_gem, -value) #무게를 제외한 값만 heappush하여 넣어준다(최대힙 구성)
    
    if capable_gem: #gem 최소보다는 작지만 넣을 수 있는 보석들은 있는 경우
        total_value -= heapq.heappop(capable_gem)
    elif not gem: #남은 보석이 한 개도 없는 경우
        break

print(total_value)