[백준 1202] 보석 도둑(Python) / G2

문제

1202.보석 도둑

코드

# 1202번
import heapq

N, K = map(int,input().split())
# [보석무게, 가격]
jew = []
for _ in range(N):
    heapq.heappush(jew, list(map(int,input().split())))
bag = [int(input()) for _ in range(K)]
bag.sort()

res = 0
temp = []
for i in bag:
    while jew and i >= jew[0][0]:
        # 최대힙
        heapq.heappush(temp, -heapq.heappop(jew)[1])
    if temp:
        res -= heapq.heappop(temp)
print(res)

코드 설명

가방을 크기가 작은 순으로 정렬하여, 가방 안에 보석이 들어가면 temp에 최대힙으로 넣어주었다. heapq는 최소힙 형태이므로 최대힙을 구현하기 위해 보석 가격을 음수형태로 저장해주었다.
가방 안에 들어갈 수 있는 모든 보석을 받은 후, 그 중에 제일 큰 보석을 꺼내 res에 빼주었다. (음수로 저장했으므로 사실상 더해준것)