프로그래밍 문제를 통해 알고리즘적 사고를 발전시키는 것은 많은 개발자와 프로그래머들에게 중요한 일입니다. 백준 온라인 저지에서 제공하는 문제 중 하나인 19942번 “다이어트” 문제는 식재료의 조합을 통해 특정 영양소를 충족하면서도 비용을 최소화하는 문제로, 효율적인 알고리즘 설계와 문제 해결 능력을 기르는 데 유용합니다.
이번 글에서는 이 문제의 접근 방법과 해결 과정을 자세히 살펴보도록 하겠습니다.
문제의 이해
19942번 문제는 주어진 식재료의 조합을 통해 단백질, 탄수화물, 지방, 비타민의 각 영양소를 일정 이상 충족해야 합니다. 각 식재료는 특정한 영양소와 비용을 가지므로, 목표는 영양소를 만족하는 조합을 찾되, 그 조합의 비용이 최소가 되도록 하는 것입니다.
이 문제는 조합을 생성하는 과정에서 영양소의 총합을 계산하고, 이를 기준과 비교하는 방식으로 해결할 수 있습니다. 문제를 해결하기 위해서는 다음과 같은 정보를 사전에 알아두어야 합니다.
| 영양소 | 기준값 |
|---|---|
| 단백질 | 100g |
| 탄수화물 | 200g |
| 지방 | 50g |
| 비타민 | 30mg |
위 표는 각 영양소의 기준값을 나타내며, 이 값을 초과하는 조합을 찾아야 합니다. 또한 각 식재료에 대한 정보도 필요합니다.
| 식재료 번호 | 단백질(g) | 탄수화물(g) | 지방(g) | 비타민(mg) | 비용(원) |
|---|---|---|---|---|---|
| 1 | 50 | 30 | 10 | 10 | 2000 |
| 2 | 40 | 50 | 20 | 20 | 3000 |
| 3 | 60 | 70 | 30 | 5 | 4000 |
| 4 | 30 | 20 | 25 | 15 | 2500 |
| 5 | 70 | 60 | 35 | 10 | 3500 |
| 6 | 20 | 10 | 5 | 25 | 1500 |
이제 각 식재료에 대한 정보를 바탕으로 조합을 만들어 영양소를 충족하는지 확인해야 합니다. 문제를 해결하기 위해서는 모든 조합을 탐색해야 하며, 이 과정에서 비트마스킹 기법이나 재귀를 사용하여 효율성을 높일 수 있습니다.
접근 방식
효과적으로 문제를 해결하기 위해서는 다음과 같은 접근 방법을 사용할 수 있습니다.
-
비트마스킹을 이용한 조합 생성: 모든 조합을 생성하기 위해 비트마스킹 기법을 사용할 수 있습니다. 각 식재료를 사용하거나 사용하지 않는 경우를 비트로 표현하여, 모든 조합을 탐색하는 것입니다. 예를 들어, 6개의 식재료가 있다면 0부터 63까지의 숫자를 사용하여 조합을 생성할 수 있습니다.
-
재귀를 통한 조합 탐색: 재귀를 활용하여 각 식재료를 선택하거나 선택하지 않는 경우로 나누어 탐색하는 방법도 있습니다. 이 경우, 현재 선택한 식재료의 영양소를 누적하여 기준값을 초과하는지 확인하게 됩니다.
-
영양소 합산 및 비교: 조합을 생성한 후, 각 조합의 영양소를 합산하고, 기준값과 비교하여 충족되는지 확인합니다. 이때 비용도 함께 계산하여 최소 비용을 업데이트합니다.
-
최소 비용 조합 추적: 영양소 기준을 만족하는 조합 중에서 최소 비용을 가진 조합을 추적하기 위해 변수에 저장합니다. 이때, 사전순으로 가장 빠른 조합을 유지해야 합니다.
이러한 방법을 통해 효율적으로 조합을 탐색하고 영양소를 만족하는지를 확인할 수 있습니다.
코드 구현
문제를 해결하기 위한 코드는 다음과 같이 작성할 수 있습니다. 아래 코드는 비트마스킹을 이용한 접근 방식을 기반으로 합니다.
“`python
N, P, C, F, V = map(int, input().split())
foods = [tuple(map(int, input().split())) for _ in range(N)]
min_cost = float(‘inf’)
best_combination = []
for i in range(1 << N):
total_protein = total_carb = total_fat = total_vitamin = 0
total_cost = 0
current_combination = []
for j in range(N):
if i & (1 << j):
total_protein += foods[j][0]
total_carb += foods[j][1]
total_fat += foods[j][2]
total_vitamin += foods[j][3]
total_cost += foods[j][4]
current_combination.append(j + 1)
if (total_protein >= P and total_carb >= C and total_fat >= F and total_vitamin >= V):
if total_cost < min_cost:
min_cost = total_cost
best_combination = current_combination
elif total_cost == min_cost:
best_combination = min(best_combination, current_combination)
if best_combination:
print(min_cost)
print(*best_combination)
else:
print(-1)
“`
위 코드는 비트마스킹을 통해 모든 조합을 생성하고, 각각의 조합에 대해 영양소를 계산하여 기준을 만족하는 조합을 찾습니다. 최소 비용을 가지는 조합이 발견되면 이를 출력하며, 만족하는 조합이 없을 경우 -1을 출력합니다.
최종 결과 및 결론
백준 19942번 “다이어트” 문제는 조합을 사용하여 영양소를 충족하면서 최소 비용을 찾는 알고리즘 문제입니다. 이 문제를 통해 비트마스킹 기법과 재귀 호출을 통한 조합 탐색의 중요성을 이해할 수 있습니다.
프로그래밍 대회나 알고리즘 학습을 위한 좋은 연습 문제가 될 것입니다. 이 글에서는 문제의 접근 방법과 코드 구현을 통해 해결 과정을 상세히 설명하였습니다.
이러한 문제를 해결하는 과정은 개발자로서의 사고력을 키우고, 더 나아가 실제 업무에서도 유용하게 활용될 수 있습니다. 프로그래밍 문제 해결에 대한 흥미를 잃지 않고 지속적으로 도전해 보시기 바랍니다.
