문제
접근
분명 DP 처럼 생겼는데, 아니다.
문제 조건 중에 한 가방에는 최대 한 개의 보석만 담을 수 있다고 명시되어 있다.
그럼 가방의 개수만큼 for문을 돌면 될 것 같다.
for문이 한번 돌때마다 가방을 하나씩 채우면 된다.
어떻게 채워야할까?
우선 작은 가방부터 차례대로 채워야하는건 확실하다.
가방을 우선 정렬해두고 작은 가방부터 하나씩 채워나간다.
그렇다면 이제 가방 한 개를 선택했을 때 해당 가방에 어떤 보석을 담는지가 중요하다.
어짜피 하나만 담을 수 있으니, 담을 수 있는 무게들 중에 가장 가치가 큰 보석을 담는 것이 항상 이득이 된다.
이러한 문제를 그리디 알고리즘(탐욕법)이라고 한다.
현재 가방의 용량이 w라고 했을 때, w보다 작은 무게를 가지는 보석들 중 가장 가치가 큰 보석을 찾아서 담아준다.
이를 가방의 개수만큼 반복하면 되는데, 그냥 찾기에는 시간이 오래걸린다.
가방 하나를 채울 때마다 보석들을 전부 확인하려면 O(N)이 걸리고 가방을 모두 반복하면 O(NK) 이다.
N과 K가 크기 때문에, 아마 시간초과에 걸릴 것 같다.
이를 해결하기 위해 우선 순위 큐를 사용했다.
보석의 무게를 기준으로 우선 순위 큐에 담아두면 현재 남은 보석 중에 가장 가벼운 순서대로 큐에서 꺼낼 수 있다.
현재 가방의 용량을 w라고 하면, 보석의 무게가 w를 넘을 때까지 큐에서 계속 꺼내서, 새로운 우선 순위 큐에 담아준다.
새로운 우선 순위 큐는 현재 가방에 담을 수 있는 보석을 담고 있다.
이 큐는 보석의 가치를 이용해서 최대힙으로 만들어 준다.
이렇게하면 현재 담을 수 있는 보석 중 가치가 가장 높은 보석으로 큐에서 O(1) 시간에 꺼낼 수 있다.
가방을 정렬해두었으므로, 다음 가방은 항상 새로 만든 우선 순위 큐에 들어있는 보석들을 담을 수 있음을 보장한다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import sys
import heapq
input = sys.stdin.readline
n, k = map(int,input().split(' '))
gem = []
for _ in range(n):
m, v = map(int, input().split(' '))
heapq.heappush(gem, (m, v))
bagSize = [int(input()) for _ in range(k)]
bagSize = sorted(bagSize)
answer = 0
possible_gem = []
for i in range(k):
bag = bagSize[i]
while gem and bag >= gem[0][0]:
m, v = heapq.heappop(gem)
heapq.heappush(possible_gem, -v)
if possible_gem:
answer -= heapq.heappop(possible_gem)
print(answer)