[힙] 1202번 보석 도둑

1. 문제

2. 나의 풀이

다른 사람의 풀이를 참고하여 품

import sys
import heapq
# from queue import PriorityQueue

N, K = [int(x) for x in sys.stdin.readline().split()]

jewelry = []
bags = []

for _ in range(N):
    weight, value = [int(x) for x in sys.stdin.readline().split()]
    heapq.heappush(jewelry, [weight, value])
for _ in range(K):
    capacity = int(sys.stdin.readline())
    heapq.heappush(bags, capacity)

total_value = 0
capable_jewelry = []

for _ in range(K):
    capacity = heapq.heappop(bags)

    while jewelry and capacity >= jewelry[0][0]:
        [weight, value] = heapq.heappop(jewelry)
        heapq.heappush(capable_jewelry, -value) # 최대힙

    if capable_jewelry:
        total_value -= heapq.heappop(capable_jewelry)
    elif not jewelry:
        break
print(total_value)

3. 남의 풀이

• https://codingfull.tistory.com/22
  
• https://claude-u.tistory.com/343
  

4. 느낀 점