보석 도둑 (백준 1202, 파이썬)

 

한 가방에는 딱 하나의 보석만 담을 수 있기 때문에 최대한 비싼 보석을 하나라도 더 챙기는것이 중요하다.

 

비싼 보석인데 무겁다고 해서 더 싸고 가벼운 보석에게 가방을 양보하면 그 가방에 다른 보석을 더 담을 수 있는것도 아니기 때문에 양보한 의미가 없기 때문이다. 비싼 보석이 무겁더라도 담을만한 가방이 있다면 우선 담아야 한다.

 

포인트는 최대한 비싼 보석부터 최대한 작은 가방에 담는 것이다.

 

이 문제는 우선순위 큐를 이용해야 한다.

 

우선순위 큐에는 가방의 최대 크기를 넘기지 않는 무게의 모든 보석을 가격을 우선순위로 담은 후에

 

가방의 수만큼 꺼내면 된다.

 

import sys
from queue import PriorityQueue
 
n, k = map(int, sys.stdin.readline().split())
 
jew = []
bag = []
for i in range(n):
    jew.append(list(map(int, sys.stdin.readline().split())))
for i in range(k):
    bag.append(int(sys.stdin.readline()))
jew.sort(key = lambda item: item[1], reverse = True) 
for i in range(n):
    jew[i].insert(0, i) 
 
jew.sort(key = lambda item: item[1])  
bag.sort() 
q = PriorityQueue()
 
idx = 0
sum = 0
for i in range(k):  
    while (idx < n and bag[i] >= jew[idx][1]):  
        q.put((jew[idx][0], jew[idx][2]))
 
        idx += 1
    if not q.empty():
       sum += q.get()[1]
print(sum)