프로그래머스

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

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

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

구매 조합을 비트마스크로 표현하고 제한된 상태 공간을 완전탐색해야 하므로 Level 3으로 판단한다.

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]다.

구매 선택만 탐색해도 되는 이유

하나의 mask를 고정하면 구매 비용과 각 스테이지의 보유 힌트 수가 결정된다. 문제에서 힌트를 더 사용할수록 해결 비용이 엄격히 낮아지므로, 보유한 힌트를 일부러 남기는 선택은 최적일 수 없다. 각 스테이지에서는 허용량 n - 1을 넘지 않는 선에서 가능한 힌트를 모두 사용하면 된다.

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

따라서 별도로 힌트 사용량을 분기할 필요가 없다. 모든 번들 구매 조합 2^(n - 1)개를 평가하고 총비용의 최솟값을 고르면 가능한 전략을 빠짐없이 비교한 셈이다. 각 조합은 새 hint_count와 비용으로 계산해야 이전 마스크의 값이 다음 조합에 섞이지 않는다.

복잡도

번들 수는 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으로 제한한다.
  • 마지막 스테이지에서는 번들을 구매할 수 없지만, 앞에서 구매한 힌트권은 사용할 수 있다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 번들 구매가 비용을 낮추는 경우와 구매하지 않는 경우를 비교할 수 있다.

assert solution([[10, 0], [10, 0]], [[5, 2]]) == 15
assert solution([[1, 0], [1, 0]], [[5, 2]]) == 2

4. 참고 풀이 비교

  • be-senior-developer의 풀이는 n이 최대 16이므로 힌트 번들을 살지 말지의 모든 경우를 완전탐색하는 방향을 설명한다.

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

마무리

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

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

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