백준: 1202 보석 도둑

문제

1202번: 보석 도둑

 

문제 풀이

 보석점에 각 보석에 대한 무게와 가격이 주어진다. 또한, K개의 가방에 각각 담을 수 있는 무게가 정해져 있다. 이때 훔칠 수 있는 보석의 최대 가격을 구하는 것이다. 이 문제는 평범한 배낭과 달리, heap을 이용하여 푸는 문제이다. heap의 성질과 Python에서 사용되는 `heapq`를 이해하고 있다면 어렵지 않게 풀 수 있다.

 

• 보석과 가방을 무게 순으로 정렬한다.
• 가방의 무게 제한보다 보석의 무게가 작다면, heap에 넣는다.
  • heapify를 할 때, 최대 힙으로 만들어야 하므로 무게를 음수로 하여 root node의 값이 최대 값이 되도록 한다.
• 즉, 무게 제한이 가장 작은 가방부터 무게가 가장 작은 보석부터 들어가는지 확인하여 최대 값으로 만들 수 있다.

 

코드

from sys import stdin
import heapq


if __name__ == "__main__":
    WEIGHT, PRICE = 0, 1
    n, k = map(int, stdin.readline().split())
    gem = sorted([list(map(int, stdin.readline().split())) for _ in range(n)])
    bag = sorted(int(stdin.readline()) for _ in range(k))

    heap = []
    cur_gem = answer = 0

    for weight_limit in bag:
        while cur_gem < n and weight_limit >= gem[cur_gem][WEIGHT]:
            # 최대 힙을 만들기 위해 음수로.
            heapq.heappush(heap, -gem[cur_gem][PRICE])
            cur_gem += 1

        if heap:
            answer += -heapq.heappop(heap)

    print(answer)