1202 보석 도둑

🥇 1202 보석 도둑

문제

---

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 $M_i$와 가격 $V_i$를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 $C_i$이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.
상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 N과 K가 주어진다. ($1 ≤ N, K ≤ 300,000$)
다음 N개 줄에는 각 보석의 정보 $M_i$와 $V_i$가 주어진다. ($0 ≤ M_i, V_i ≤ 1,000,000$)
다음 K개 줄에는 가방에 담을 수 있는 최대 무게 $C_i$가 주어진다. ($1 ≤ C_i ≤ 100,000,000$)
모든 숫자는 양의 정수이다.

출력

---

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

예제

---

입력 1	출력 1	입력 2	출력 2
2 1	10	3 2	164
5 10		1 65
100 100		5 23
11		10
		2

분석

---

상덕이는 가방의 최대 무게에 맞게 보석을 담아 최대한 많이 훔쳐야 한다. 이 부분에서 그리디 문제라는 것을 알 수 있으며, 각 가방의 최대 무게에 맞게 하나만 담아야 한다.
현재 가장 capacity가 작은 가방에 담을 수 있는 모든 보석의 후보 중 value가 가장 큰 보석을 합해 주고, 모든 가방에 하나씩 담길 때까지 확인해주면 된다.

• 가방에 담을 수 있는 보석 찾기 : 보석 무게를 기준으로 하는 minheap
• 그 보석 중 가장 비싼 보석 찾기 : maxheap

소스 코드

---

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

# 보석점에 있는 보석 개수, 상덕이가 갖고있는 가방 개수
n, k = map(int, input().split())

bijou = []
# 각 보석의 정보 m(무게), v(가격)
for _ in range(n):
    m, v = map(int, input().split())
    heappush(bijou, [m, v])

# 가방에 담을 수 있는 최대 무게 c, 가방당 하나만 담을 수 있다.
backpacks = [int(input()) for _ in range(k)]
backpacks.sort()

total_value = 0 # 훔칠 수 있는 보석의 가격 총 합
candidate = [] # 지정된 가방에 넣을 수 있는 보석의 가격
for capacity in backpacks:
    # 훔칠 보석이 남아 있고 보석의 무게가 가방의 용량보다 적거나 같으면
    while bijou and bijou[0][0] <= capacity:
        w, v = heappop(bijou)
        heappush(candidate, -v) # max

    if candidate:
        total_value -= heappop(candidate)

print(total_value)