[BOJ] 백준 1202번 보석 도둑 - 파이썬(Python)

문제

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

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

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

입력

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

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

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

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

출력

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

 

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

💡 풀이 및 코드

import heapq
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
arr = []
bag = []

for i in range(n):
    heapq.heappush(arr, tuple(map(int, input().split())))
for i in range(k):
    bag.append(int(input()))
bag.sort()

result = 0
temp = []
for b in bag:
    while arr and b >= arr[0][0]:
        heapq.heappush(temp, -heapq.heappop(arr)[1])
    if temp:
        result -= heapq.heappop(temp)
    elif not arr:
        break
print(result)

처음접해보는 배낭 문제였다. 아이디어를 떠올리는데에 어려움을 겪어 복습이 필요할 것 같다.

풀이과정을 설명하자면, 

오름차순 정렬된 배낭마다 반복문을 돌며 넣을 수 있는 보석의 가격을 힙 큐에 넣고 이중 가장 값비싼 보석을 채택하는 방식이다. 이때, 배낭이 수용가능한 보석을 힙 큐에 넣을 때는 최소힙, 힙 큐에 들어있는 보석 중 큰 값을 선택할 때는 최대힙을 사용한다.