[백준][자료구조/힙] 1202. 보석도둑(파이썬/Python)

import sys
import heapq
input = sys.stdin.readline


n,k = map(int,input().split())
bag = []
jewely = []
candidate = []
answer = 0

for _ in range(n):
    weight, price = map(int,input().split())
    heapq.heappush(jewely,[weight,price])

for _ in range(k):
    bag.append(int(input()))

bag.sort()

for i in bag:
    while jewely and i >= jewely[0][0]:
        weight, price = heapq.heappop(jewely)
        heapq.heappush(candidate,-price)

    #for문을 돌 때만, 그러니까 딱 가방수만큼만 최대힙으로 저장된 값이 answer에 더해짐
    if candidate:
        answer -= heapq.heappop(candidate)
print(answer)

 

[나름의 해석]

• 가방의 수만큼만 돌아야 하기에 가방을 기준으로 반복문을 돌리는 것이다.
• 또한 가방의 수만큼 돌아가는 동안 jewely(일반적으로 heap이라고 생각해도 됨)에 저장된 weight가 지금 도는 가방이 버틸 수 있는 무게보다 작은 값들을 모두 candidate(후보자)라는 리스트에 넣어준다
• 그 후 마지막에 제일 작은 값(음수로 넣어주었기 때문에)부터 꺼내 가방의 수만큼만 나오게 한다.
•  bag.sort()를 해주는 이유는 아마도 힌트 때문일 것이다.