[맛있는물회] [파이썬] <백준 알고리즘> 1202번 "보석 도둑"

문제 조건

---

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

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

 

Input

---

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

 

Output

---

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

 

생각한 아이디어

---

흠... 

평범한 배낭 문제를 풀다가 0/1 knapsack 문제를 더 풀어보려고 검색했는데 이 문제가 나왔다.

근데 knapsack으로 접근하면 못푸는 문제다ㅜㅜㅜㅜ

그리디, 우선순위 큐 문제이다.

 

처음에 DP로만 접근을 해서 꽤나 고생을 했다. 

 

우선순위 큐를 사용하면 어느정도 로직을 가지고 그리디로 접근하면 된다.

 

1. 먼저 가방을 오름차순으로 정렬한다.

2. 보석들을 무게기준으로 오름차순으로 정렬한다.

3. 이제 가방을 차례대로 들고오면서 가방에 넣을 수 있는 보석들은 HEAP에 push한다. 

     3-1 만약 보석을 다 돌았거나, 현재 보석이 가방에 들어가지 않으면 그만둔다.

4. 이제 가방에 넣을 수 있는 보석들이 우선순위 큐에 의해서 가장 큰 값이 나오게 된다. 그 값을 RESULT에 더해준다.

    4-1 여기서 좀 참고한 알고리즘은 이 부분이다. 파이썬에서는 HEAP이 MIN heap이다. 즉, 작은 값을 index 0에 올려준다. 그래서 값을 음수처리해서 heap에 넣어주면 빼낼때 뺄셈으로 계산을 해주면 MAX heap으로 사용가능하다.

5. 그렇게 모든 가방을 차례대로 계산해주면 된다.

 

 

여기서 이러한 로직이 가능한 이유는 가방의 무게가 오름차순으로 정렬되어 있기 때문이다.

즉, 이전의 가방에 넣을 때 넣을 수 있는 보석들 중 가장 큰 값을 넣었다.

그리고 그 다음 가방에는 들어갈 수 있는 보석들을 추가해주지만, 이전의 가방에 들어갈 수 있는 보석 또한 존재한다. 

이전의 가방 보다 현재의 가방이 더 크기 때문에 이전 가방에 들어갈 수 있는 보석은 무조건 현재 가방에서도 가능하다. 따라서 이러한 HEAP 사용이 가능하다.

 

 

소스코드

#1202 보석 도둑
import sys
import heapq
from collections import deque
input=sys.stdin.readline

n,k=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=deque(sorted(arr,key=lambda k: k[0]))
bags=[int(input()) for _ in range(k)]
bags=sorted(bags)
heap=[]
res=0

for bag in bags:
    capacity=bag
    while arr and capacity >=arr[0][0]:
        heapq.heappush(heap,-arr.popleft()[1])
    if heap:res-=heapq.heappop(heap)
print(res)

 

*파이썬 문법 정리