문제 요약
1번부터 n번까지의 스테이지를 순서대로 모두 해결해야 한다.
각 스테이지는 사용한 힌트권 개수에 따라 해결 비용이 달라진다.
힌트권을 많이 사용할수록 스테이지 해결 비용은 감소한다.
cost[i][j]위 값은 i + 1번 스테이지에서 힌트권을 j개 사용했을 때의 해결 비용을 의미한다.
각 힌트권에는 사용할 수 있는 스테이지 번호가 정해져 있다.
예를 들어 3번 힌트권은 3번 스테이지에서만 사용할 수 있다.
마지막 스테이지를 제외한 각 스테이지에서는 힌트 번들을 최대 하나 구매할 수 있다.
힌트 번들에는 이후 스테이지에서 사용할 수 있는 힌트권이 들어 있다.
모든 스테이지를 해결하는 데 필요한 최소 비용을 구해야 한다.
핵심 아이디어
각 스테이지에서 판매하는 힌트 번들에 대해 선택지는 두 가지다.
- 구매한다.
- 구매하지 않는다.
힌트 번들을 판매하는 스테이지는 1번부터 n - 1번까지다.
따라서 가능한 구매 조합의 수는 다음과 같다.
2^(n - 1)제한사항에서 n <= 16이므로 최대 구매 조합의 수는 다음과 같다.
2^15 = 32,768따라서 모든 힌트 번들 구매 조합을 직접 확인할 수 있다.
각 구매 조합마다 스테이지를 1번부터 순서대로 진행하면서 다음 비용을 계산하면 된다.
스테이지 해결 비용 + 구매한 힌트 번들 가격왜 모든 힌트권을 사용해도 될까?
문제에서 다음 조건이 주어진다.
cost[i][j] > cost[i][j + 1]즉, 힌트권을 더 많이 사용할수록 스테이지 해결 비용이 항상 작아진다.
또한 i번 힌트권은 오직 i번 스테이지에서만 사용할 수 있다.
따라서 현재 스테이지의 힌트권을 나중을 위해 남겨둘 이유가 없다.
가지고 있는 힌트권은 현재 스테이지에서 가능한 만큼 모두 사용하는 것이 항상 유리하다.
단, 하나의 스테이지에서 사용할 수 있는 힌트권은 최대 n - 1개다.
따라서 실제 사용하는 힌트권 수는 다음과 같다.
used_hint = min(hint_count[stage], n - 1)비트마스크로 구매 조합 표현하기
각 스테이지의 힌트 번들을 구매했는지 비트로 표현한다.
예를 들어 n = 5라면 구매 가능한 힌트 번들은 1번부터 4번 스테이지까지 총 4개다.
0000: 아무 번들도 구매하지 않음
0001: 1번 스테이지 번들만 구매
0010: 2번 스테이지 번들만 구매
0101: 1번, 3번 스테이지 번들 구매
1111: 모든 번들 구매stage번 스테이지의 번들을 구매했는지는 다음과 같이 확인할 수 있다.
mask & (1 << stage)비트가 0이 아니라면 해당 번들을 구매하는 경우다.
스테이지 처리 순서
각 구매 조합에 대해 스테이지를 1번부터 차례대로 처리한다.
스테이지마다 다음 순서로 계산해야 한다.
- 현재 가지고 있는 해당 번호의 힌트권을 사용한다.
- 스테이지 해결 비용을 더한다.
- 현재 스테이지의 힌트 번들을 구매하기로 했다면 번들 가격을 더한다.
- 번들에 포함된 이후 스테이지의 힌트권을 추가한다.
힌트 번들은 현재 스테이지를 해결한 후 구매한다.
또한 번들에는 항상 현재보다 뒤에 있는 스테이지의 힌트권만 포함되어 있다.
따라서 스테이지를 앞에서부터 순서대로 처리하면 힌트권 상태를 정확하게 계산할 수 있다.
힌트 정보 해석하기
예를 들어 다음 힌트 번들이 있다고 하자.
hint[i] = [40, 2, 3, 3]의미는 다음과 같다.
- 번들 가격:
40 - 2번 힌트권: 1장
- 3번 힌트권: 2장
번들을 구매하면 다음과 같이 처리한다.
total += hint[i][0]
for ticket in hint[i][1:]:
hint_count[ticket - 1] += 1같은 번호의 힌트권이 여러 장 들어 있을 수 있으므로 모든 원소를 하나씩 확인해야 한다.
전체 알고리즘
0부터2^(n-1) - 1까지 모든 비트마스크를 확인한다.- 각 구매 조합마다 스테이지별 힌트권 개수를 0으로 초기화한다.
- 스테이지를 1번부터
n번까지 순서대로 진행한다. - 현재 스테이지에서 사용할 수 있는 힌트권 수를 계산한다.
- 해당 힌트 개수에 맞는 해결 비용을 더한다.
- 현재 스테이지의 번들을 구매하는 조합이면 가격을 더하고 힌트권을 지급한다.
- 모든 스테이지를 처리한 총비용 중 최솟값을 반환한다.
전체 코드
def solution(cost, hint):
n = len(cost)
answer = float("inf")
# 1번부터 n-1번 스테이지까지의 번들 구매 조합을 모두 확인한다.
for mask in range(1 << (n - 1)):
hint_count = [0] * n
total = 0
for stage in range(n):
# 한 스테이지에서 사용할 수 있는 힌트권은 최대 n-1개다.
used_hint = min(hint_count[stage], n - 1)
total += cost[stage][used_hint]
# 마지막 스테이지에서는 힌트 번들을 판매하지 않는다.
if stage == n - 1:
continue
# 현재 스테이지의 힌트 번들을 구매하는 경우다.
if mask & (1 << stage):
total += hint[stage][0]
for ticket in hint[stage][1:]:
ticket_index = ticket - 1
# n-1개를 초과한 힌트권은 사용할 수 없으므로
# 저장할 때부터 최대 n-1개로 제한해도 된다.
if hint_count[ticket_index] < n - 1:
hint_count[ticket_index] += 1
answer = min(answer, total)
return answer코드 설명
모든 구매 조합 확인
for mask in range(1 << (n - 1)):구매 가능한 번들은 총 n - 1개다.
따라서 2^(n-1)개의 구매 조합을 확인한다.
힌트권 개수 저장
hint_count = [0] * nhint_count[i]는 현재 가지고 있는 i + 1번 스테이지의 힌트권 개수를 의미한다.
각 구매 조합은 서로 독립적이므로 새로운 조합을 확인할 때마다 0으로 초기화한다.
스테이지 해결 비용 계산
used_hint = min(hint_count[stage], n - 1)
total += cost[stage][used_hint]가지고 있는 힌트권은 모두 사용하지만, 최대 사용 개수는 n - 1개다.
cost[stage][used_hint]를 더해 현재 스테이지를 해결한다.
번들 구매 여부 확인
if mask & (1 << stage):현재 스테이지에 해당하는 비트가 켜져 있으면 번들을 구매한다.
번들 가격과 힌트권 반영
total += hint[stage][0]
for ticket in hint[stage][1:]:
ticket_index = ticket - 1
if hint_count[ticket_index] < n - 1:
hint_count[ticket_index] += 1첫 번째 원소는 번들 가격이고, 이후 원소들은 번들에 들어 있는 힌트권 번호다.
같은 번호가 여러 번 등장하면 해당 스테이지의 힌트권을 여러 장 받는다.
시간 복잡도
힌트 번들 구매 조합은 다음과 같다.
2^(n - 1)각 구매 조합마다 n개의 스테이지와 각 번들의 힌트권 목록을 확인한다.
번들 하나에 포함된 힌트권 수를 최대 k라고 하면 시간 복잡도는 다음과 같다.
O(2^(n - 1) x n x k)제한사항에서 다음 조건을 만족한다.
n <= 16
k <= 19최대 구매 조합 수가 32,768개이므로 충분히 처리할 수 있다.
공간 복잡도
각 구매 조합에서 스테이지별 힌트권 개수를 저장하는 배열만 사용한다.
O(n)정리
이 문제의 핵심은 n의 크기가 작다는 점을 이용하는 것이다.
각 스테이지의 힌트 번들을 구매할지 말지 결정해야 하므로 비트마스크로 모든 구매 조합을 표현할 수 있다.
핵심 포인트는 다음과 같다.
- 구매 가능한 힌트 번들은
n - 1개다. - 전체 구매 조합은 최대
2^15 = 32,768개다. - 각 구매 조합마다 스테이지를 순서대로 진행한다.
- 힌트권은 지정된 스테이지에서만 사용할 수 있으므로 보관할 이유가 없다.
- 해결 비용은 힌트권을 많이 사용할수록 항상 감소한다.
- 한 스테이지에서는 힌트권을 최대
n - 1개까지만 사용할 수 있다. - 번들 가격과 스테이지 해결 비용을 모두 더한 값의 최솟값을 구한다.
복잡한 DP를 만들기보다 제한사항을 확인하고 모든 구매 조합을 탐색하는 것이 가장 단순하고 안전한 풀이이다.
