하.....
저번 주에 풀었던 문제들이 어째 다 하나같이 곤란했었어서... 온전히 내 힘으로 푼 문제가 별로 없다.
N개의 보석이 있고 K개의 가방이 있다. 각각의 보석에는 무게 M과 가격 V가 있고, 각각의 가방에는 최대로 담을 수 있는 무게가 정해져있다. 가방에는 각각 하나의 보석만 담을 수 있다.
이 때, 최대의 가치로 보석을 담으려 할 때, 담을 수 있는 보석의 최대 가치의 합을 출력한다.
일반적인 Knapsack 문제...로 생각하고 시작했으나, 일반적이지는 또 않은.
우선 Priority Queue를 이용하는 문제이다.
생각보다 시간 조건이 매우 빡빡해서, 처음 생각했던 풀이법은 시간 초과가 발생하였다.
→ 시간초과.
4번 시간을 줄이겠다고 binary search(O(logN)
)도 구현을 했는데... 아무리 해도 시간 초과가 해소되지를 않아서, 총체적으로 다른 풀이를 고안해야했다. 결국 구글링.
prioity queue에서 원소를 넣고 꺼내는 과정 자체도 시간 복잡도가 O(logN)
이나, 원소의 개수(N)이 적다 보니 접근법 1보다 효율적인 모양.
import heapq
import sys
input = sys.stdin.readline
N, K = map(int, input().split(" "))
jewel = []
bag = []
for i in range(N) :
M, V = map(int, input().split(" "))
heapq.heappush(jewel, (M, V))
for j in range(K) :
heapq.heappush(bag, int(input()))
sum = 0
tmpJewel = []
while bag :
curBag = heapq.heappop(bag)
while jewel and jewel[0][0] <= curBag :
heapq.heappush(tmpJewel, -heapq.heappop(jewel)[1])
if tmpJewel :
sum += -heapq.heappop(tmpJewel)
elif not jewel :
break
print(sum)
풀이를 알고 나니 해결 자체는 어렵지 않았다. python에서의 priority queue는 heapq를 사용하는데, min heap으로만 기능하기 때문에, max heap을 사용해야할 경우 -1 값을 곱해서 값을 저장해주고, 값을 꺼낼 때 다시 -1을 고쳐주는 것으로 해결하였다.