155. 보석 도둑

백준

1. 우선순위 큐

import heapq
import sys

n, k = map(int, input().split())
jewelries = []
for _ in range(n):
    weight, value = map(int, sys.stdin.readline().split())
    heapq.heappush(jewelries, (weight, value))

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

total = 0 
can_put_in = [] #현재 bag의 capacity보다 작은 모든 보석들

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

print(total)

2. C++