[BOJ] 1202 보석 도둑

thoho·2023년 1월 8일
0

코딩 문제 풀이

목록 보기
6/13

1202. 보석 도둑 문제 링크
문제 풀이 코드 링크

하.....
저번 주에 풀었던 문제들이 어째 다 하나같이 곤란했었어서... 온전히 내 힘으로 푼 문제가 별로 없다.


문제 요약

N개의 보석이 있고 K개의 가방이 있다. 각각의 보석에는 무게 M과 가격 V가 있고, 각각의 가방에는 최대로 담을 수 있는 무게가 정해져있다. 가방에는 각각 하나의 보석만 담을 수 있다.
이 때, 최대의 가치로 보석을 담으려 할 때, 담을 수 있는 보석의 최대 가치의 합을 출력한다.


풀이

일반적인 Knapsack 문제...로 생각하고 시작했으나, 일반적이지는 또 않은.
우선 Priority Queue를 이용하는 문제이다.

생각보다 시간 조건이 매우 빡빡해서, 처음 생각했던 풀이법은 시간 초과가 발생하였다.

접근법 1(실패)

  1. 가방을 담을 수 있는 무게의 오름차순으로 배열한다.
  2. 보석을 가치의 내림차순으로 배열한다.
  3. 가치가 큰 보석부터 하나씩 pop한다.
  4. 가방 배열에서 해당 보석을 담을 수 있는 가방 중에서 가장 작은 가방을 찾는다.

→ 시간초과.

4번 시간을 줄이겠다고 binary search(O(logN))도 구현을 했는데... 아무리 해도 시간 초과가 해소되지를 않아서, 총체적으로 다른 풀이를 고안해야했다. 결국 구글링.

접근법 2

  1. 가방을 담을 수 있는 무게의 오름차순으로 배열한다.
  2. 보석을 무게의 오름차순으로 배열한다.
  3. 새로운 priority queue를 만들어서, 제일 앞에 있는 가방(제일 들어가는 무게가 작은)에 대해 해당 가방보다 가벼운 보석을 모두 해당 priority queue에 넣는다. 순서는 가치의 내림차순.
  4. 모든 보석이 다 들어갔다면, priority queue에서 원소를 pop한다. 해당 원소가 해당 가방에 들어갈 수 있는 가장 비싼 보석.
  5. 3~4를 모든 가방에 대하여 반복.

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을 고쳐주는 것으로 해결하였다.

profile
어떻게든 굴러가고 있는

0개의 댓글