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

1202번: 보석 도둑

---

 

Heap을 사용하자!

처음에는 보석 무게 minheap을 만들어 가능한 보석을 찾고 그중에서 maxheap을 통해 가장 큰 가치를 찾는다.

 

1. 보석들을 [무게, 가치]를 담는 minheap(jewel)을 생성한다.
2. 가방은 bag에 담아 허용치순으로 정렬해준다.
3. 보석의 가치를 담는 maxheap(candidate)를 생성한다.
4. 작은 가방부터 돌면서 가장 무게가 작은 보석(jewel[0][0])이 가방에 들어간다면 계속 candidate에 넣어준다.
5. 가치가 가장 큰 보석을 candidate에서 뽑아준다.

 

 

import sys
import heapq
input = sys.stdin.readline
 
N, K = map(int, input().split())
jewel = []
bag = []
for _ in range(N):
    heapq.heappush(jewel, list(map(int, input().split())))
for _ in range(K):
    bag.append(int(input()))
 
bag.sort()
 
result = 0
candidate = []
for b in bag:
    while jewel and b >= jewel[0][0]:
        w, v = heapq.heappop(jewel)
        heapq.heappush(candidate, -v)
 
    if candidate:
        result -= heapq.heappop(candidate)
 
print(result)