프로그래머스

프로그래머스 힌트 스테이지 풀이: 비트마스크 완전탐색

작성자: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 힌트 스테이지
  • 출처: 프로그래머스, 2025 카카오 하반기 2차
  • 자체 판단 난이도: Level 4

문제 원문과 제한 조건은 변경될 수 있으므로 제출 전에는 공식 문제 페이지를 다시 확인하세요.

1. 문제 요약

n개의 스테이지를 1번부터 순서대로 클리어해야 합니다. 각 스테이지는 사용한 힌트권의 개수에 따라 해결 비용이 달라집니다.

각 스테이지에서는 힌트 번들을 최대 하나 구매할 수 있습니다. 번들은 이후 스테이지에서 사용할 수 있는 여러 장의 힌트권을 제공하고, 구매 비용이 발생합니다. 힌트권 번호가 i라면 i번 스테이지에서만 사용할 수 있습니다.

모든 스테이지를 클리어하는 최소 비용을 구해야 합니다. 비용에는 다음 두 종류가 포함됩니다.

  • 스테이지를 해결하는 비용
  • 구매한 힌트 번들의 가격

힌트 번들은 살 수도 있고 사지 않을 수도 있으며, 같은 번호의 힌트권이 여러 장 포함될 수 있습니다. 스테이지 수가 최대 16이므로 각 번들의 구매 여부를 부분집합으로 표현할 수 있습니다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

구매 조합을 비트마스크로 표현하기

마지막 스테이지를 제외한 n - 1개 스테이지에서 힌트 번들을 구매할 수 있습니다. 각 번들의 구매 여부를 비트 하나로 표현합니다.

예를 들어 번들이 4개라면 다음과 같이 표현할 수 있습니다.

mask = 0101

이는 1번과 3번 스테이지의 번들을 구매하고, 2번과 4번 스테이지의 번들은 구매하지 않는다는 뜻입니다.

가능한 모든 구매 조합은 0부터 2 ** (n - 1) - 1까지 순회하면 됩니다. n ≤ 16이므로 최대 32,768개의 조합만 확인하면 됩니다.

구매 조합으로 스테이지별 힌트 수 계산

하나의 구매 조합을 선택하면 구매한 번들에 포함된 힌트권을 모두 세어 스테이지별 보유 개수를 계산합니다.

hint_count[stage] += 1

힌트권은 자신과 같은 번호의 스테이지에서만 사용할 수 있으므로, i번 스테이지에서 사용할 수 있는 힌트 수는 hint_count[i]입니다.

항상 사용할 수 있는 힌트권을 모두 사용

문제의 조건에서 힌트권을 많이 사용할수록 해결 비용이 작아지고, cost[i][j] > cost[i][j + 1]이 보장됩니다. 따라서 현재 스테이지에서 사용 가능한 힌트권이 x장이라면, 최대 허용 개수인 n - 1을 넘지 않는 범위에서 모두 사용하는 것이 항상 이득입니다.

used = min(hint_count[stage], n - 1)
stage_cost = cost[stage][used]

이 성질 덕분에 “힌트권을 몇 장 사용할지”를 별도로 선택할 필요 없이, 구매 조합으로 계산된 보유 개수만 사용하면 됩니다.

정당성

구매 조합 하나를 고정하면 각 스테이지의 보유 힌트 수와 번들 구매 비용이 모두 결정됩니다. 또한 해결 비용은 힌트 사용량이 늘어날수록 엄격히 감소하므로 보유 힌트를 일부 남기는 선택은 최적해가 될 수 없습니다.

따라서 모든 구매 조합의 비용을 계산하고 그중 최솟값을 선택하면 가능한 모든 전략을 빠짐없이 비교한 것이며, 최솟값이 곧 정답입니다.

복잡도

번들 수를 n - 1이라고 하면 구매 조합은 2 ** (n - 1)개입니다. 각 조합에서 번들 내용과 스테이지를 확인하는 데 O(n²) 시간이 걸리므로 전체 시간 복잡도는 O(2^n × n²)입니다. 추가 공간 복잡도는 O(n)입니다.

핵심 관찰

구매 여부가 정해지면 힌트권을 몇 장 사용할지도 자동으로 정해집니다. 비용이 힌트 사용량에 따라 항상 감소하므로 각 스테이지에서 보유한 힌트를 허용량까지 모두 사용하는 것이 최적입니다. 따라서 탐색할 선택은 번들 구매 조합 하나로 줄어듭니다.

오답 접근과 반례

힌트권으로 줄어든 스테이지 비용만 세고 번들 가격을 더하지 않으면 틀립니다. 번들을 사지 않아 비용이 10인 경우와 가격 5를 내고 스테이지 비용이 4가 되는 경우의 실제 비용은 각각 10과 9입니다.

3. 문제 해결 코드 (Python)

def solution(cost, hint):
    n = len(cost)
    bundle_count = n - 1
    answer = float('inf')

    for mask in range(1 << bundle_count):
        hint_count = [0] * n
        total = 0

        for stage in range(bundle_count):
            if mask & (1 << stage):
                bundle = hint[stage]
                total += bundle[0]

                for target_stage in bundle[1:]:
                    hint_count[target_stage - 1] += 1

        for stage in range(n):
            used = min(hint_count[stage], n - 1)
            total += cost[stage][used]

        answer = min(answer, total)

    return answer

구현 포인트

  • mask의 각 비트는 해당 스테이지에서 힌트 번들을 구매했는지를 나타냅니다.
  • 힌트 번들의 첫 번째 값은 가격이므로 total에 더하고, 나머지는 힌트권 번호입니다.
  • 힌트권 번호는 1부터 시작하므로 배열 인덱스로 사용할 때 target_stage - 1을 적용합니다.
  • 한 스테이지에서 사용할 수 있는 힌트권은 최대 n - 1장이므로 min으로 제한합니다.
  • 마지막 스테이지에서는 번들을 구매할 수 없지만, 앞에서 구매한 힌트권은 사용할 수 있습니다.

4. 동일한 문제를 어떻게 풀었나 웹검색 하여 요약

공개된 풀이들은 구매할 번들의 조합을 탐색하고, 현재까지 모은 힌트권 수를 이용해 각 스테이지의 비용을 계산하는 완전탐색·백트래킹 방식으로 접근합니다.

백트래킹은 스테이지를 진행하면서 보유 힌트 수를 갱신하고 마지막에 비용을 비교하는 방식입니다. 이 글에서는 같은 구매 조합을 비트마스크 하나로 표현해 모든 조합을 순회합니다. 두 방식은 본질적으로 같은 상태 공간을 탐색하지만, 비트마스크는 구매 여부를 저장하고 조합별 힌트 수를 다시 계산한다는 점이 다릅니다.

마무리

이 문제에서 중요한 관찰은 힌트권 사용량을 별도로 결정할 필요가 없다는 점입니다. 번들 구매 조합만 정해지면 각 스테이지의 최적 사용량은 자동으로 정해집니다.

스테이지 수가 16으로 작기 때문에 복잡한 최단 경로 알고리즘보다 비트마스크로 가능한 구매 조합을 빠짐없이 비교하는 방법이 적합합니다. 현재 상태를 어떤 정보로 압축할 수 있는지 찾는 것이 이 문제의 핵심입니다.

#비트마스크#프로그래머스#난이도 4