BOJ 1202: 보석 도둑 [Python 3]

굉장히 직관적인 문제라고 생각했는데, 너무나도 어려운 Dynamic Programming 문제였다.

가방의 개수, 그리고 각 가방에 담을 수 있는 무게가 정해져 있다.

최대의 value를 가지는 보석들을 가방에 넣어서 훔치는게 목표이다.

출력은 총 훔친 보석들의 value이다.

 

import sys
import heapq
input= sys.stdin.readline
n,k=map(int,input().split())
weightandvalue=[list(map(int,input().split())) for _ in range(n)]
maxweight=[int(input()) for _ in range(k)]
weightandvalue.sort()
temp=[]
answer=0
for bag in maxweight:
    while weightandvalue and weightandvalue[0][0]<=bag:
        heapq.heappush(temp,-heapq.heappop(weightandvalue)[1])
    if temp:
        answer-=(heapq.heappop(temp))
print(answer)

이 문제는 heap을 통해서 해결했다.

모든 input들을 받고, 보석에 대한 정보를 무게에 대해서 sort한다.

가방들을 직접 하나씩 보면서, 가방의 최대 무게가 보석들의 무게보다 크면,

우선 '베낭에 가져갈 수 있는 임시 리스트'에 담는다.

이 과정에서 최대 힙을 사용해서, pop을 했을 때 value가 제일 큰 값이 튀어나올 수 있도록 한다.

만약 보석의 무게가 해당 베낭의 최대 무게를 벗어나면, 아까 넣었던 '임시 리스트'에 최대의 value의 보석을 뽑아서 가방에 넣는다.

 

heap을 잘 이용하면 sort하는 것 보다 더욱 시간 복잡도가 낮게 문제를 해결할 수 있었다.