[백준 1202] 보석 도둑 (Python)

백준 1202-보석도둑

코드

import sys
import heapq

N, K = map(int, sys.stdin.readline().split())
jew = []
for _ in range(N):
    heapq.heappush(jew, list(map(int, sys.stdin.readline().split())))
bags = []
for _ in range(K):
    bags.append(int(sys.stdin.readline()))
bags.sort()

answer = 0
tmp_jew = []
for bag in bags:
    while jew and bag >= jew[0][0]:
        heapq.heappush(tmp_jew, -heapq.heappop(jew)[1])
    if tmp_jew:
        answer -= heapq.heappop(tmp_jew)
    elif not jew:
        break
print(answer)

풀이

문제를 푸는 아이디어는 다음과 같다.
각 가방에 담을 수 있는 최대 가치의 보석을 담되 용량이 작은 가방부터 보석을 담는다.
가방의 순서를 신경쓰지 않고 보석을 담는다면 보석을 담지 못하는 경우가 생긴다.
예를 들어
보석 = [(1, 20), (2, 100), (5, 50)
가방 = [10, 2]
일 때 용량이 10인 가방에 가장 가치가 큰 무게가 2인 보석을 담으면 남은 용량이 2인 가방에는 무게가 1인 보석밖에 담을 수 없고 이때 최대 가치는 120이다.
하지만 용량이 2인 가방부터 보석을 담는다면 최대 가치는 150이 된다.
따라서 용량이 작은 가방부터 순서대로 보석을 담아야 하는 것이다.

그리고 이 아이디어를 구현할 때 최대힙과 최소힙을 사용한다.
가방들을 용랑의 오름차순으로 정렬했을 때
각 가방에 담을 수 있는 모든 보석을 찾을 때 최소힙을 사용하고
각 가방에 넣을 수 있는 보석 중 가장 가치가 큰 보석을 찾을 때 최대힙을 이용한다.

피드백 환영합니다.
-끝-