[백준] 1202 보석 도둑 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/1202
• 🔑 힙, 우선순위 큐
  • 1. 입력받은 보석들을 무게 기준 오름차순 정렬
  • 2. 가방도 오름차순 정렬
  • 3. 가장 작은 가방부터 시작해서 이 가방에 담을 수 있는 보석이면 힙에 보석 가격을 담는다. (음수로 담는다. 최대힙)
  • 4. 담긴 보석이 있으면 가장 비싼 보석을 선택한다.
  • 3, 4번 과정을 가방 개수만큼 반복한다.
  • 크기가 작은 가방부터 담기 때문에 보석을 모두 담고 뽑아내는 게 가능하게 된다.
    • 크기가 2인 가방에 담을 수 있는 보석이면 크기가 3인 가방에도 담을 수 있다.
    • 가방 크기 = [2, 10]
    • 보석 = [(1, 65), (2, 99), (5, 23)]
    • 가방 크기 2일 때 힙 = [-99, -65]
    • -99를 뽑아서 정답으로 올리면 힙에 [-65] 남음
    • 가방 크기 10일 때 힙 = [-65, -23]
    • -65를 뽑아서 정답으로 올린다.
    • 이런 프로세스를 거친다.

 

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

n, k = map(int, input().split())

jewelry = []

for _ in range(n):
    m, v = map(int, input().split())
    jewelry.append((m, v))

bag = [int(input()) for _ in range(k)]

jewelry.sort()  # 무게 오름차순 정렬
bag.sort()      # 가방 크기 오름차순 정렬

idx, answer = 0, 0
price = []      # 보석 가격 담을 힙

for b in bag:

    while idx < len(jewelry) and b >= jewelry[idx][0]:  # i번 가방에 담을 수 있는 보석 다 담기
        heappush(price, -jewelry[idx][1])
        idx += 1

    if price:   # 담은 보석이 있으면 가장 비싼 보석을 선택
        answer += -heappop(price)

print(answer)