[백준] 보석 도둑 (python)

출처 : https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

풀이 방법

문제에서 핵심은 정렬과 그리디이다. 

가방을 넣을 수 있는 가능한 무게로 오름차순으로 정렬한 후 수용가능한 무게가 낮은 가방부터 채워주어야 한다. 

왜냐하면 만약 가능한 가방이 10, 5(무게) 이렇게 2개 있고 보석이 (5, 100), (7, 7) (무게, 가격) 이렇게 2개가 있다고 가정을 했을 때 10인 가방부터 채운다면 가능한 보석 중 가격이 가장 비싼 (5, 100)인 보석이 들어가게 되면 (7, 7)인 보석을 담을 수가 없다 그러므로 정렬 후 5인 가방부터 채우며 넣을 수 있는 보석 중 가장 비싼 보석부터 채워주게 된다면 2개의 보석을 그리디 하게 넣을 수 있다. 

현재 가방에 담을 수 있는 최대 가격 보석을 선택하기 위해 우선순위 큐를 사용했다. 

max heap을 사용하기 위해 -가격을 저장했다.

import heapq
N, K = map(int, input().split())
bag = [0 for _ in range(K)]
jewel = [[0, 0] for _ in range(N)]
pq = []
answer = 0
for i in range(N):
    w, v = map(int, input().split()) ## 무게, 가격 
    jewel[i][0] = w
    jewel[i][1] = v
for i in range(K):
    bag[i] = int(input())
bag.sort() ## 가방 무게 오름 차순 정렬
jewel.sort(key = lambda x: (x[0], -x[1])) ##  무게는 오름차순 가격은 내림차순
j = 0
for i in range(K): ## 가방 순회 
    while(j < N and bag[i] >= jewel[j][0]):  ## 현재 가방 무게보다 보석이 가벼우면 
        heapq.heappush(pq, -jewel[j][1]) ## 힙에 추가 -가격으로 저장해서 max heap으로 이용
        j += 1        
    if pq:
        answer -= heapq.heappop(pq) ## -가격으로 저장했으므로 다시 양수로 바꾼 후 더하기 
print(answer)