정올 다이어트

문제

예제

import sys
input = sys.stdin.readline

n = int(input())
mp, mf, ms, mv = map(int, input().split())
INF = float('inf')

foods = []
for _ in range(n):
    foods.append(tuple(map(int, input().split()))) 
min_cost = INF
best_combination = []

def solve(idx, p, f, s, v, cost, path):
    global min_cost, best_combination

    if p >= mp and f >= mf and s >= ms and v >= mv:
        if cost < min_cost:
            min_cost = cost
            best_combination = path[:]
        elif cost == min_cost:
            if path < best_combination:
                best_combination = path[:]
        return

    for i in range(idx, n):
        np, nf, ns, nv, c = foods[i]
        solve(i + 1, p + np, f + nf, s + ns, v + nv, cost + c, path + [i + 1]) 

solve(0, 0, 0, 0, 0, 0, [])

if min_cost == INF:
    print(-1)
else:
    print(min_cost)
    print(*sorted(best_combination))

이 코드는 여러 개의 식재료 중 일부를 선택하여, 주어진 최소 영양소 요구량을 만족하면서 총 비용이 최소가 되는 조합을 찾는 프로그램이다. 먼저 사용자로부터 식재료의 개수와 요구되는 단백질, 지방, 탄수화물, 비타민의 최소량을 입력받고, 각 식재료가 제공하는 영양소와 비용 정보를 리스트에 저장한다. 그런 다음 재귀함수 solve를 이용해 현재 인덱스에서 시작해 가능한 모든 식재료 조합을 탐색하며, 누적된 영양소 값이 조건을 만족할 경우 비용이 더 작거나, 같은 비용일 때 사전순으로 빠른 경우를 선택해 최적의 결과를 갱신한다. 모든 탐색이 끝난 후 최소 비용이 초기값인 무한대일 경우 조건을 만족하는 조합이 없음을 의미하므로 -1을 출력하고, 그렇지 않으면 최소 비용과 해당 조합의 인덱스를 오름차순으로 출력하도록 구성되어져 있다.