세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 와 가격 를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.
상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.
첫째 줄에 N과 K가 주어진다. ()
다음 N개 줄에는 각 보석의 정보 와 가 주어진다. ()
다음 K개 줄에는 가방에 담을 수 있는 최대 무게 가 주어진다. ()
모든 숫자는 양의 정수이다.
첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.
입력 1 | 출력 1 | 입력 2 | 출력 2 |
---|---|---|---|
2 1 | 10 | 3 2 | 164 |
5 10 | 1 65 | ||
100 100 | 5 23 | ||
11 | 10 | ||
2 |
상덕이는 가방의 최대 무게에 맞게 보석을 담아 최대한 많이 훔쳐야 한다. 이 부분에서 그리디 문제라는 것을 알 수 있으며, 각 가방의 최대 무게에 맞게 하나만 담아야 한다.
현재 가장 capacity가 작은 가방에 담을 수 있는 모든 보석의 후보 중 value가 가장 큰 보석을 합해 주고, 모든 가방에 하나씩 담길 때까지 확인해주면 된다.
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)