백준 1202번(G2) : 보석 도둑

문제

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

풀이

먼저, 용량이 작은 가방은 넣을 수 있는 보석의 수가 적으므로, 아예 작은 가방부터 보석을 채워 넣는 전략을 세울 수 있다.

그러면 각 가방마다 넣을 수 있는 보석 중 가장 비싼 보석을 넣도록 구현하면 된다.

 

이를 위해 우선 가방을 용량 순으로, 보석을 무게 순으로 정렬한 후 각 가방마다 넣을 수 있는 보석을 heap 에 넣는다.

 

이때 heap이 가격에 대한 max heap 이라면, pop를 했을 때 가장 비싼 보석을 가방에 넣게 된다.

선택되지 않은 보석들은 더 큰 가방에는 여전히 들어가므로 그대로 heap에 두고, 다음 가방에 대해서도 똑같이 수행하면 된다. 

 

제출 코드

 

import sys
import heapq
input = sys.stdin.readline

N, K = map(int, input().split())
jewels = []
for _ in range(N):
    weight, value = map(int, input().split())
    jewels.append((weight, value))
jewels.sort(key=lambda x: x[0]) 

bags = [int(input()) for _ in range(K)]
bags.sort() 

ans = 0
max_heap = []
j = 0

for bag in bags:
    while j < N and jewels[j][0] <= bag:
        heapq.heappush(max_heap, -jewels[j][1])
        j += 1 
        #j를 초기화하지 않기 때문에 보석은 한 번씩만 heap에 들어간다.
    if max_heap:
        ans -= heapq.heappop(max_heap) 

print(ans)