[python 백준 1202] 보석 도둑

처음에 시도하려 했던 방법(실패)

1. 보석들을 Tuple pair로 이루어진 List를 만든다. ([(1, 65), (5, 23), (2, 99)])
2. 보석의 무게가 높은 순으로 정렬 ([(2, 99), (1, 65), (5, 23)])
3. 가방 무게가 큰 순으로 정렬 ([10, 2])
4. 가방에 들어갈 수 있는 보석 무게를 무거운 순으로 넣고 List에서 제거
   => 시간초과

우선순위 큐로 문제를 풀어야했다.

코드

import sys
import heapq

N, B = map(int, sys.stdin.readline().split())

heap = []

for i in range(N):
    heapq.heappush(heap, list(map(int, sys.stdin.readline().split())))

B_list = [int(sys.stdin.readline()) for i in range(B)]
B_list.sort()

res = 0
tmp_heap = []

# 적게 나가는 가방 무게부터 탐색
for B_weight in B_list:
    # 아직 넣지 못한 보석이 있고, 가방 무게보다 작거나 같은 보석이라면(최소힙)
    while heap and B_weight >= heap[0][0]:
        heapq.heappush(tmp_heap, -heapq.heappop(heap)[1])
    if tmp_heap:
        # 기본적으로 최소힙으로 작동하기 때문에 21번째 줄에 -를 붙임(최대힙)
        res += -heapq.heappop(tmp_heap)
print(res)

 

입력값 예시

보석 : [(1, 65), (2, 99), (5, 80)]
가방 : [10, 2]

<가방의 무게가 큰 순서대로 보석을 넣을 경우>
가방 무게 : 10 -> 들어간 가격 : (2, 99)
가방 무게 : 2 -> 들어간 가격 : (1, 65)

총 보석값 : 164

---

<가방의 무게가 작은 순서대로 보석을 넣을 경우>
가방 무게 : 2 -> 들어간 가격 : (2, 99)
가방 무게 : 10 -> 들어간 가격 : (5, 80)

총 보석값 : 179

 

가방의 무게에 따라 보석값이 달라지므로 가방의 무게가 작은 순서대로 넣어야한다.

보석 무게 : 최소힙

보석 값 : 최대힙

 

최대힙과 최소힙을 사용해야한다.