[Baekjoon]백준 1202 보석 도둑(골드 2) - Python

문제설명

예제

문제를 살펴보면 가방에는 최대 하나의 보석만 넣을 수 있으며 각 보석당 가격이 주어진다

최종적으로 가방에 최대한 비싼 보석들을 가져가 최대 가격이 되는 것이 목표이다

 

일단 보석정보를 하나의 리스트로 저장해주었다 map으로 무게와 가격을 입력받고, [무게, 가격]을 append해주었다

이후 가방의 크기를 입력받은 후에 보석정보과 가방의 크기가 저장된 리스트를 정렬해준다

-> 효율적으로 값을 확인할 수 있기때문

 

이후 각 가방을 순차적으로 확인하면서 현재 가방에 들어갈 수 있는 보석들을 최대힙에 넣는다

최대힙에 넣을 때는 가격을 음수로 넣어야하는데, heapq는 최소힙이기 때문에 이를 최대힙으로 사용하기위해서

음수로 값을 넣어주어야한다

힙에서 pop하여 가장 비싼 보석을 선택해 가방에 담고 가격을 누적하여 최대값을 갱신하게된다

최종적으로 해당 과정을 반복하면 보석 가격의 최대 합을 구할 수 있다

import sys
input = sys.stdin.readline
import heapq

n, k = map(int, input().split())
jew = []
for _ in range(n):
    jew_weight, jew_price = map(int, input().split())
    jew.append([jew_weight, jew_price])
jew.sort()
bag = []
for _ in range(k):
   bag.append(int(input()))
bag.sort()

j = 0
result = 0
heap = []
for i in bag:
    while j < n and jew[j][0] <= i:
        heapq.heappush(heap, -jew[j][1])
        j += 1
    if heap:
        result += -heapq.heappop(heap)
        
print(result)