백준 1202번 - 보석 도둑

보석 도둑 문제 바로 가기

풀이 날짜: 2026-03-22

baekjoon 알고리즘 문제 풀이

풀이 코드


import heapq
import sys
input = sys.stdin.readline

n,k = map(int, input().split())
weight = []

for _ in range(n):
    m,v = map(int, input().split())
    heapq.heappush(weight, (m,v))

bags = []
for _ in range(k):
    c = int(input())
    bags.append(c)

bags.sort()

candidate = []
answer = 0

for c in bags:
    while weight and weight[0][0] <= c:
        m,v = heapq.heappop(weight)
        heapq.heappush(candidate, -v)

    if candidate:
        answer += -heapq.heappop(candidate)

print(answer)

접근 방법

이 문제는 보석의 무게와 가격이 주어지고, 각 가방마다 담을 수 있는 최대 무게가 있을 때, 각 가방에 하나의 보석만 넣을 수 있으며 전체 가격의 합을 최대화하는 문제이다. 처음에는 단순히 가격이 높은 보석부터 선택하려고 했지만, 가방마다 무게 제한이 다르기 때문에 단순 정렬로는 해결되지 않는다는 점을 깨달았다. 결국 “현재 가방에 들어갈 수 있는 보석 중 가장 비싼 것”을 선택해야 한다는 조건이 핵심이었다.

핵심 아이디어 - 힙 구조 + 그리디

가방을 작은 순서대로 처리하면서, 현재 가방에 들어갈 수 있는 보석들을 후보군에 넣고 그 중 가장 비싼 보석을 선택하는 것이다. 이를 위해 두 개의 힙을 사용한다. 하나는 보석을 무게 기준으로 관리하기 위한 힙이고, 다른 하나는 후보 보석 중 가장 비싼 값을 빠르게 꺼내기 위한 힙이다.

무게 기준 힙 사용 이유

보석을 (무게, 가격) 형태로 최소 힙에 넣으면, 항상 가장 가벼운 보석부터 꺼낼 수 있다. 이를 통해 현재 가방의 용량보다 작은 보석들을 순차적으로 확인할 수 있다. 특히 weight[0][0]을 통해 현재 가장 가벼운 보석의 무게를 확인할 수 있다는 점이 중요하다. 이 구조 덕분에 불필요한 반복 없이 조건에 맞는 보석만 효율적으로 처리할 수 있다.

가격 기준 힙 사용 이유

현재 가방에 들어갈 수 있는 보석은 여러 개일 수 있기 때문에, 그 중 가장 가격이 높은 보석을 선택해야 한다. 하지만 파이썬의 heapq는 최소 힙이므로, 가격을 음수로 넣어 최대 힙처럼 사용한다.

전체 알고리즘 흐름

가방을 오름차순으로 정렬한 뒤, 각 가방에 대해 다음 과정을 반복한다. 먼저 현재 가방에 들어갈 수 있는 모든 보석을 무게 힙에서 꺼내 가격 힙에 넣는다. 그 다음, 가격 힙이 비어있지 않다면 가장 비싼 보석을 하나 꺼내 정답에 더한다. 이 과정을 반복하면 전체 가격의 최대값을 구할 수 있다.

내가 헷갈렸던 포인트

처음에는 heapq를 사용하면 자동으로 정렬된 리스트처럼 유지될 것이라고 생각했는데, 실제로는 힙 구조일 뿐 전체 정렬이 보장되지 않는다는 점에서 혼동이 있었다. 또한 (m, v) 형태로 넣었을 때 튜플의 첫 번째 값 기준으로 정렬된다는 점도 중요한 포인트였다. 그리고 가방을 입력 순서대로 처리했을 때 틀린 결과가 나왔는데, 반드시 가방을 오름차순으로 정렬해야 한다는 점이 핵심이었다.

핵심 정리

이 문제는 단순 정렬이 아니라, “조건을 만족하는 후보를 계속 누적하면서 그 중 최적을 선택하는 구조”라는 점이 중요하다. 따라서 무게 기준 힙으로 후보를 관리하고, 가격 기준 힙으로 최적 값을 선택하는 이중 힙 구조가 핵심이다. 특히 “가방을 작은 것부터 처리한다”는 그리디 전략이 정답을 보장하는 핵심 아이디어였다.

Vienna sausage