[백준]_1202번 : 보석 도둑(파이썬)

1202번: 보석 도둑

먼저 무게와 가격 중에서 무엇을 더 중시할 것인지 알아야 한다. 우리가 최종적으로 원하는 것은 훔칠 수 있는 최대 값어치의 보석이지만 가방의 무게 한계를 고려하지 않으면 무용지물이다. 즉 가격은 무게 다음으로 중요한 요소이다. 무게(w)와 가격(v)을 튜플로 묶어서 힙큐(tag)에 push 해준다.

 

이후에 tag에서 무게가 적은 순서로 보석이 나올 것이다. 이제 보석을 담아야 하는데 가능하다면 무게 한계($C_{i}$)가 작은 가방부터 보석을 담아 주는 것이 바람직하다. $C_{i}$를 저장하는 리스트를 limit이라고 하자.

tag에 (5, 100), (3, 50)인 보석이 있고 limit에는 3, 5가 있다고 가정하자. 만약 (3, 50)을 한계가 5인 가방에 담아버리면 우리는 더 이상 보석을 담을 수 없다(이상적인 답은 50+100=150 임에도 불구하고...). 그래서 가능하면 무게가 적은 가방부터 다뤄주어야 한다. 즉 limit을 오름차순 정렬해야 한다.

import heapq
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
tag = []
for _ in range(N): heapq.heappush(tag, tuple(map(int, input().split())))
limit = [int(input()) for _ in range(K)]
limit.sort()

 

이제부터 limit에서 작은 값을 순서로 뽑는다. 이때 뽑힌 값을 L이라고 하자.

 

tag[0][0](tag에서 가장 무게가 적은 보석)이 L보다 작은 동안에 heappop을 반복한다. 이때 heappop 한 값들 중에서 가격에 해당하는 부분을 새로운 리스트 tmp에 heappush 한다. 즉 tmp에는 L 가방에 들어갈 자격이 충분한 보석들의 가격들로 차있다. 하지만 문제는 그냥 heappush를 하면 최솟값이 튀어나올 것이기 때문에 음수를 붙인 상태로 heappush 해준다.

 

$w_{i}  > L$을 만족하는 $w_{i}$ 가 존재한 순간 더 이상 L에 들어갈 자격이 있는 보석은 tag에 더 이상 남아 있지 않을 것이다. 왜냐하면 무게를 기준으로 tag가 힙정렬 되어 있기 때문이다.

 

이제 tmp에서 heappop을 해줘서 가장 큰 원소를 steal 변수에서 빼준다(tmp에 가격들이 음수로 들어갔기 때문). 이 과정을 계속 반복해 주면 된다.

 

주의해야 할 것은 tmp를 초기화하면 안 된다. 왜냐하면 tmp에 한번 저장된 가격들은 앞으로 나올 가방 무게(L)에 모두 들어갈 수 있기 때문이다.

 

최종 코드 >>

import heapq
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
tag = []
for _ in range(N): heapq.heappush(tag, tuple(map(int, input().split())))
limit = [int(input()) for _ in range(K)]
limit.sort()

tmp = []
steal = 0
for L in limit:
    while tag and L >= tag[0][0]:heapq.heappush(tmp, -heapq.heappop(tag)[1])
    if tmp:steal -= heapq.heappop(tmp)
    elif not tag:break
print(steal)