[백준] 1202번 - 보석 도둑

1. 문제 요약

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

• 보석 N개 (무게 M, 가격 V)
• 가방 K개 (각 가방은 하나의 보석만 담을 수 있음)
• 가방마다 최대 무게 제한 존재

→ 목표: 담을 수 있는 보석 가격 합의 최대값

---

2. 처음 접근 (실패)

처음에는 이렇게 생각했다.

“가장 비싼 보석부터 넣으면 되지 않을까?”

그래서 구현:

heapq.heappush(jewels, (-v, m)) # 가치 기준 최대힙

 

그리고:

if bags[0] >= m:
	heapq.heappop(bags)

 

---

 문제점

이 방식은 보석 중심 사고였다.

• 가치 높은 보석부터 꺼냄
• 가장 작은 가방 하나만 보고 넣을지 결정

 문제:

뒤에 있는 더 큰 가방에 들어갈 수 있는 보석도 그냥 버려짐

---

 핵심 반례

2 2
10 100
2 99
2
10

 

내 코드 결과:

• 100 → 가방 2 못 들어감 → 버림
• 99 → 가방 2에 넣음

결과: 99

 

정답:

• 99 → 가방 2
• 100 → 가방 10

결과: 199

---

3. 두 번째 접근 (또 실패)

이번엔 반대로 생각했다.

“작은 보석부터 넣으면 되지 않을까?”

 

heapq.heappush(jewels, (m, -v)) # 무게 기준

 

---

 문제점

이번에는 작은 보석을 너무 빨리 사용해버림

---

 반례

3 2
1 1
2 100
3 99
2
3

 

내 코드:

• (1,1) → 가방 2 사용
• (2,100) → 가방 3 사용

결과: 101

 

정답:

• (2,100) → 가방 2
• (3,99) → 가방 3

결과: 199

---

4. 깨달음

이 문제는 보석을 고르는 문제가 아니라,

각 가방에 어떤 보석을 넣을지를 결정하는 문제

---

 잘못된 접근

보석 → 가방 찾기

 

---

 올바른 접근

가방 → 넣을 보석 선택

 

---

5. 최종 해결 전략

핵심 아이디어

1. 가방을 작은 순서대로 처리
2. 현재 가방에 들어갈 수 있는 보석들을 모음
3. 그중 가장 가치가 큰 보석 선택

---

6. 구현 코드

 

import heapq
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
jewels = list(sorted(tuple(map(int, input().split())) for _ in range(n)))
bags = list(sorted(int(input()) for _ in range(k)))
candidate = []
cost = 0
index = 0

for bag in bags:
    while index < n and jewels[index][0] <= bag:
        heapq.heappush(candidate, -jewels[index][1])
        index += 1
    
    if candidate:
        cost -= heapq.heappop(candidate)

print(cost)

---

7. 시간복잡도

• 정렬: O(N log N + K log K)
• 힙 연산: O((N+K) log N)

총: O((N+K) log N)