[Baekjoon] 1202. 보석 도둑

🔗 Problem Link

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

---

❔Thinking

• 보석의 무게와 가격이 주어질 때, 가방에 보석 하나씩만을 담아 최대 가격을 반환한다.

---

💻Solution

import heapq
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
jewels = []
bags = []

for _ in range(N):
    weight, value = map(int, input().split())
    jewels.append((weight, value))

for _ in range(K):
    bags.append(int(input()))

jewels.sort() 
bags.sort()

max_heap = []
total_value = 0
j = 0

# 가방을 하나씩 처리
for bag in bags:
    # 현재 가방에 넣을 수 있는 모든 보석을 힙에 추가
    while j < N and jewels[j][0] <= bag:
        heapq.heappush(max_heap, -jewels[j][1])
        j += 1

    if max_heap:
        total_value += -heapq.heappop(max_heap)

print(total_value)

---

🗝️keypoint

1. 해당 가방에 담을 수 있는 모든 보석 가운데에서 가장 높은 가격의 보석을 하나씩 담아 나간다.
2. 현재 가방의 무게까지 가능한 모든 보석을 담고, 가장 높은 가격을 반환하는 heapq를 만들어 push와 pop을 반복한다.