[Python] boj no. 1202 : 보석 도둑

Problem

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

Idea

훔칠 수 있는 보석들의 최대 가격을 얻기 위해서는 보석이 들어갈 수 있는 가방에 가능한 가방이 담을 수 있는 최고 가격의 보석을 담아야 한다. 이 때, 가방의 크기가 작을수록 들어갈 수 있는 보석의 종류가 한정적이므로 우선적으로 보석을 배정해 주어야 할 것이다.

우선 보석과 가방을 무게에 따라 오름차순으로 정렬한다. 보석은 최소힙을, 가방은 리스트를 정렬하는 것으로 구현했다. 이후 가방 리스트를 순회하면서 가방의 무게보다 작은 보석을 힙에서 빼 보석의 가격을 기준으로 하는 최대 힙에 저장한다.

다음과 같은 작업을 수행하면 최대 힙의 전단에 위치한 보석은 해당 가방이 담을 수 있는 최대 가치의 보석이다. 이를 모든 가방에 대해서 수행한 뒤 선택된 보석들의 가격을 더하면 훔칠 수 있는 보석의 최대 가격을 얻을 수 있다.

Code

import sys
import heapq

N, K = map(int, sys.stdin.readline().split())

minh = []
for _ in range(N):
    m, v = map(int, sys.stdin.readline().split())
    heapq.heappush(minh, (m, v))

bag = [int(sys.stdin.readline()) for _ in range(K)]
bag.sort()  # 가방 크기를 오름차순 정렬

maxh = []
sum = 0
for i in bag:
    while minh and i >= minh[0][0]: # 가방 무게보다 작은 무게의 보석들(minh)을 모두 maxh 에 넣음
        m, v = heapq.heappop(minh)
        heapq.heappush(maxh, (-v, v))

    if maxh:
        sum += heapq.heappop(maxh)[1] # maxh의 최상위 인덱스 값은 현재 혹은 이후의 가방에 들어갈 수 있는 보석들 중 가장 높은 가치의 보석

print(sum)

Comment