1. 문제 설명

보석 도둑

2. 문제 분석

우선순위 큐를 통해 현재 가방에 담을 수 있는 보석을 가격이 큰 순서대로 정렬하자. 이때 min-heap과 max-heap을 사용 목적에 따라 모두 사용할 수 있어야 한다.

1. 가방과 보석을 무게가 작은 순서대로 정렬한다. min-heap을 활용하자.
2. 담을 수 있는 무게가 작은 가방부터 하나씩 확인한다.
3. 이 가방에 담을 수 있는 무게 이하인 보석이 있다면 모두 힙에 담아두자.
4. 이 가방에 담을 수 있는 보석 중 가장 가격이 비싼 보석을 이 가방에 담자. max-heap을 활용한다.
5. 다음 꺼낼 가방은 사용한 가방보다 무게가 더 크므로, 담아 놓은 보석 역시 이 가방에 담아둘 수 있다.
6. 가방을 다 사용하거나, 담아둔 보석을 모두 사용하거나, 무게를 확인할 보석이 없을 때까지 반복하자.

• 가방 무게를 체크하면서 이전 가방(즉 무게가 더 작은 가방)에 들어갈 수 있는 보석이라면, 다음 가방에도 들어간다는 5번의 인사이트가 문제를 푸는 핵심.

3. 나의 풀이

import heapq
import sys

n, k = map(int, sys.stdin.readline().rstrip().split())

jewels = []
bags = []

for _ in range(n):
    weight, price = map(int, sys.stdin.readline().rstrip().split())
    heapq.heappush(jewels, [weight, price])

for _ in range(k):
    weight = int(sys.stdin.readline().rstrip())
    heapq.heappush(bags, weight)
# 우선순위 힙을 통해 보석과 가방을 무게 순서대로 정렬한다.

total = 0
heap = []
while bags:
    bag = heapq.heappop(bags)
    # 사용할 가방 중 무게가 가장 작은 가방
    while jewels and bag >= jewels[0][0]:
        heapq.heappush(heap, -1 * jewels[0][1])
        heapq.heappop(jewels)
        # 이 가방에 담을 수 있는 보석이 있다면 가격이 큰 순서대로 담자.
    if heap: total += -1 * heapq.heappop(heap)
    # 이 가방에 담을 보석이 존재한다면 가격이 가장 큰 보석을 꺼내서 담자
    elif not jewels: break
    # 이 가방에 담을 보석도 없고, 남은 보석도 없다면 가방이 있어도 계속 할 수 없다.

print(total)