[백준 파이썬] 1202 보석 도둑

백준 1202

가방에는 하나의 보석밖에 들어갈 수 없어 그리디로도 풀 수 있다.
가방에는 가방이 버틸수 있는 무게의 보석 중 가치가 가장 높은 것부터 들어가야한다.
먼저 가방을 오름차순으로, 보석은 무게를 기준으로 오름차순으로 정렬한다. 가능한 무게가 작은 가방부터 정렬을 해야 나중에 무거운 보석이 있을 때 큰 가방에 들어가도록 할 수 있다.
가능한 보석 중 가치가 가장 높은 보석을 가져와야 하므로 힙을 사용한다.
보석이 가방에 들어갈 수 있다면 모두 힙에 추가해주었다가 가장 가치가 높은 보석을 빼면서 최종 리스트에 추가해주면 된다.

# 1202 / 보석 도둑
import heapq

N, K = map(int, input().split())
gems = [list(map(int, input().split())) for _ in range(N)]
bags = [int(input()) for _ in range(K)]

bags.sort() 
gems.sort(key=lambda x: x[0]) # 무게 순 정렬

i = 0
total_val = 0
heap = []

for bag in bags:
    while i < N and gems[i][0] <= bag: # 현재 가방의 수용 가능 무게보다 가볍다면
        heapq.heappush(heap, -gems[i][1]) # 힙에 모두 추가
        i += 1
    if heap: # 힙에 보석이 들어있다면
        total_val -= heapq.heappop(heap, -gems[i][1]) # 가장 가치가 높은 보석 하나 추가

print(total_val)