[백준] 1202 파이썬(python) : 보석 도둑 - 이중heap

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

1202번: 보석 도둑

 

 

import sys, heapq
n, k = map(int, sys.stdin.readline().split())
jewel = []
for _ in range(n):
    heapq.heappush(jewel, list(map(int, sys.stdin.readline().split()))) #1
bags = [ int(sys.stdin.readline()) for _ in range(k) ]
bags.sort() #2
ans, tmp_maxheap = 0, [] #3
for bag_weight in bags:
    while jewel and bag_weight >= jewel[0][0]: #4
        heapq.heappush(tmp_maxheap, -heapq.heappop(jewel)[1]) #5
    if tmp_maxheap: #6
        ans += abs(heapq.heappop(tmp_maxheap))
    elif not jewel: #7
        break
print(ans)

 

#1 : 보석의 정보를 담는 리스트를 최소 힙으로 만듬

#2 : 가방을 오름차순으로 정렬

#3 : 결과값 변수와 보석의 가치를 넣어줄 임시 최대 힙 선언

#4 : 최소 힙인 jewel[0]의 첫번재 원소 jewel[0][0]은 보석의 무게를 의미하는데 보석의 무게보다 가방의 무게가 크거나 같을때

#5 : 보석의 가치를 임시 최대 힙에 삽입

#6 : 임시 최대 힙에 원소가 있다면 결과값 변수에 최댓값을 추가, 한 가방에 한 개의 보석만 들어갈 수 있으니까 한번만 실행

#7 : 최대 힙에도 원소가 없고 jewel도 바닥 났다면 break

 

어렵다. 최소 힙 하나만 사용하는게 아니라 보석의 가치 중 높은것을 먼저 넣어야해서 최대 힙도 사용해야 해서 그런것 같다. 하나는 최소 힙에 하나는 최대 힙에 넣어야 한다는 점이 이전에 풀었던 7662번(이중 우선순위 큐)문제랑 비슷한것 같다. https://hgk5722.tistory.com/282

서로 가치가 다른 두 원소를 비교해서 사용해야 한다는 점은 17503번(맥주 축제) 문제가 생각난다. https://hgk5722.tistory.com/279