백준 19942 다이어트, 3줄이면 끝나는 비트마스크 조합 풀이
백준 19942번 다이어트 문제는 N개의 식재료 중에서 최소 영양소 기준을 충족하면서 총 비용이 가장 낮은 조합을 찾는 문제입니다. 비트마스크를 사용하면 모든 조합을 단 몇 줄의 코드로 탐색할 수 있고, N이 15 이하로 제한되어 있어 2^N(최대 32,768개) 조합도 충분히 빠르게 처리됩니다. 최소 비용이 같은 조합이 여러 개라면 사전순으로 가장 앞선 조합을 출력해야 하며, 조건을 만족하는 조합이 없으면 -1을 출력합니다.
비트마스크로 모든 조합을 탐색하는 핵심 아이디어
비트마스크는 각 식재료의 선택 여부를 이진수의 비트 하나로 표현하는 방식입니다. 예를 들어 N이 5라면 0부터 31까지의 정수로 32가지 조합을 모두 나타낼 수 있습니다. 정수 i의 j번째 비트가 1이면 j번째 식재료를 선택했다는 뜻이고, 0이면 선택하지 않았다는 뜻입니다.
이 문제를 푸는 핵심 코드는 아래와 같이 아주 짧습니다. 반복문 하나로 모든 조합을 검사하고, 선택된 재료들의 영양소 합과 비용을 계산합니다.
for i in range(1 << n):
cost = 0
nutrients = [0] * 4
selected = []
for j in range(n):
if i & (1 << j):
cost += ingredients[j][4]
for k in range(4):
nutrients[k] += ingredients[j][k]
selected.append(str(j + 1))
이 코드에서 1 << n은 2^n을 의미하고, i & (1 << j)는 i의 j번째 비트가 1인지 확인하는 연산입니다. 이 방식은 재귀 함수 없이도 모든 조합을 순회할 수 있어 코드가 훨씬 간결해집니다.
사전순 출력 조건, 이렇게 해결하면 됩니다
문제에서 요구하는 사전순 출력 조건을 만족하려면 두 가지를 함께 고려해야 합니다. 첫째, 최소 비용을 갱신할 때 조합을 사전순으로 비교해야 합니다. 둘째, 비트마스크 반복문은 0부터 시작하므로 자연스럽게 선택된 식재료 번호가 작은 조합부터 탐색하게 됩니다.
사전순 비교는 파이썬의 리스트 비교 연산자를 활용하면 간단합니다. selected 리스트를 문자열로 변환한 뒤, 기존 최적 조합과 비교하여 더 작은 값을 선택합니다.
if cost < min_cost or (cost == min_cost and selected < best_selected):
min_cost = cost
best_selected = selected
여기서 주의할 점은 사전순 비교를 위해 selected 리스트를 정수 리스트가 아닌 문자열 리스트로 유지해야 한다는 것입니다. ['1', '10', '2']와 ['1', '2', '10']을 비교할 때 문자열 비교는 '10'이 '2'보다 작다고 판단하므로, 문제의 의도와 맞게 '1', '2', '10' 순서가 올바른 사전순이 됩니다.
영양소 조건 확인과 최소 비용 갱신
모든 조합을 순회하면서 선택된 재료들의 영양소 합이 최소 요구량을 충족하는지 확인해야 합니다. 영양소는 단백질, 지방, 탄수화물, 비타민 총 4가지이며, 각각의 최소 요구량을 모두 충족해야 합니다.
if nutrients[0] >= min_protein and nutrients[1] >= min_fat \
and nutrients[2] >= min_carb and nutrients[3] >= min_vitamin:
if cost < min_cost or (cost == min_cost and selected < best_selected):
min_cost = cost
best_selected = selected
조건을 충족하는 조합이 하나도 없다면 min_cost가 초기값(예: 무한대)으로 남아 있으므로 -1을 출력합니다. 이때 최소 비용이 갱신된 적이 있는지 확인하는 방법으로 초기값을 float('inf')로 설정하거나, best_selected가 비어 있는지 확인할 수 있습니다.
전체 코드와 함께 보는 문제 풀이
아래는 위에서 설명한 내용을 모두 합친 완전한 코드입니다. 입력 형식은 첫 줄에 식재료의 개수 N, 다음 줄에 최소 영양소 4가지, 이후 N줄에 각 식재료의 영양소와 비용이 주어집니다.
import sys
input = sys.stdin.readline
n = int(input())
min_protein, min_fat, min_carb, min_vitamin = map(int, input().split())
ingredients = [list(map(int, input().split())) for _ in range(n)]
min_cost = float('inf')
best_selected = []
for i in range(1 << n):
cost = 0
nutrients = [0] * 4
selected = []
for j in range(n):
if i & (1 << j):
cost += ingredients[j][4]
for k in range(4):
nutrients[k] += ingredients[j][k]
selected.append(str(j + 1))
if nutrients[0] >= min_protein and nutrients[1] >= min_fat \
and nutrients[2] >= min_carb and nutrients[3] >= min_vitamin:
if cost < min_cost or (cost == min_cost and selected < best_selected):
min_cost = cost
best_selected = selected
if best_selected:
print(min_cost)
print(' '.join(best_selected))
else:
print(-1)
이 코드는 N이 최대 15일 때 약 32,768개의 조합을 검사하므로 시간 제한 안에 충분히 통과할 수 있습니다.
재귀 방식과 비트마스크, 어떤 걸 선택해야 할까
백준 19942번 문제를 푸는 방법은 크게 두 가지로 나뉩니다. 재귀 함수를 이용한 백트래킹 방식과 비트마스크를 이용한 완전 탐색 방식입니다. 두 방식 모두 정답을 찾을 수 있지만, 각각의 특징이 있습니다.
재귀 방식은 선택하는 경우와 선택하지 않는 경우를 나누어 탐색하므로 가지치기를 통해 불필요한 탐색을 줄일 수 있습니다. 예를 들어 현재까지의 비용이 이미 최소 비용을 초과했다면 더 이상 탐색을 진행하지 않을 수 있습니다. 반면 비트마스크는 모든 조합을 무조건 검사하므로 가지치기 없이도 코드가 간결합니다.
비트마스크 방식이 특히 유리한 경우는 N이 작을 때입니다. N이 15 이하라면 2^N이 최대 32,768이므로, 이 정도 크기는 완전 탐색으로도 빠르게 처리할 수 있습니다. 반면 N이 20을 넘어가면 2^N이 100만을 넘어가므로 비트마스크보다는 재귀 방식에 가지치기를 추가하는 것이 더 효율적입니다.
문제 풀이 시 자주 하는 실수와 주의점
이 문제를 풀 때 많은 사람들이 사전순 비교에서 실수를 합니다. selected를 정수 리스트로 유지한 채 비교하면 [1, 10, 2]와 [1, 2, 10]을 비교할 때 [1, 10, 2]가 더 작다고 판단하는 문제가 생깁니다. 따라서 반드시 문자열로 변환한 뒤 비교해야 합니다.
또 하나 주의할 점은 최소 비용이 같은 조합이 여러 개일 때입니다. 비트마스크 반복문이 0부터 시작하므로 자연스럽게 작은 번호의 조합부터 탐색하게 됩니다. 하지만 사전순으로 가장 앞선 조합을 찾기 위해서는 cost == min_cost인 경우에도 selected < best_selected 조건을 확인해야 합니다.
### Q. 최소 비용 조합이 여러 개일 때 사전순 비교는 어떻게 하나요?
파이썬 리스트 비교 연산자를 사용합니다. 문자열 리스트 상태에서 selected < best_selected 비교를 통해 사전순으로 더 앞선 조합을 선택하면 됩니다. 이때 리스트의 각 요소는 문자열이어야 올바르게 비교됩니다.
### Q. N이 15보다 크면 비트마스크로 풀 수 없나요?
N이 20이 넘어가면 2^N이 100만을 넘어가므로 시간 초과가 발생할 수 있습니다. 이 경우 재귀 함수에 가지치기를 추가하는 백트래킹 방식이 더 적합합니다. 현재까지의 비용이 이미 최소 비용보다 크면 탐색을 중단하는 방식으로 효율을 높일 수 있습니다.
### Q. 영양소 조건을 충족하는 조합이 없을 때는 어떻게 하나요?
최소 비용이 초기값(무한대)으로 남아 있는지 확인하면 됩니다. best_selected가 비어 있다면 조건을 만족하는 조합이 없는 것이므로 -1을 출력합니다.