[백준 19942 🥇] 다이어트

https://www.acmicpc.net/problem/19942

19942번: 다이어트

문제

식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각각 합이 최소 100, 70, 90, 10가 되도록 하는 경우를 생각해보자. 이 경우 모든 재료를 선택하면 쉽게 해결되지만, 우리는 조건을 만족시키면서도 비용이 최소가 되는 선택을 하려고 한다.

재료단백질지방탄수화물비타민가격

1	30	55	10	8	100
2	60	10	10	2	70
3	10	80	50	0	50
4	40	30	30	8	60
5	60	10	70	2	120
6	20	70	50	4	40

예를 들어, 식재료 1, 3, 5를 선택하면 영양분은 100, 145, 130, 10으로 조건을 만족하지만 가격은 270이 된다. 대신 2, 3, 4를 선택하면 영양분의 합은 110, 130, 90, 10, 비용은 180이 되므로, 앞의 방법보다는 더 나은 선택이 된다.

입력으로 식재료 표가 주어졌을 때, 최저 영양소 기준을 만족하는 최소 비용의 식재료 집합을 찾아야 한다.

 

문제 풀이

import sys
from itertools import combinations

n=int(sys.stdin.readline())
p,f,s,v=map(int, sys.stdin.readline().strip().split(' '))
nutri=[]
for _ in range(n):
    nutri.append(list(map(int, sys.stdin.readline().strip().split(' '))))

numbers=list(range(1,n+1))
min_cost=1e9
min_idx={}

for pick in range(1,n+1):
    pick_idx=list(combinations(numbers, pick))
    isAllPass=True
    for picked in pick_idx:
        mp, mf, ms, mv = 0, 0, 0, 0
        tmp_cost = 0
        for idx in picked:
            mp+=nutri[idx-1][0]
            mf+=nutri[idx-1][1]
            ms+=nutri[idx-1][2]
            mv+=nutri[idx-1][3]
            tmp_cost+=nutri[idx-1][4]
        if mp >= p and mf >= f and ms >= s and mv >= v:
            if min_cost >= tmp_cost:
                min_cost = tmp_cost
                if min_cost in min_idx.keys():
                    min_idx[min_cost].append(picked)
                else:
                    min_idx[min_cost]=[]
                    min_idx[min_cost].append(picked)
        else:
            isAllPass = False

    # 모든 인덱스를 뽑는 경우의 수가 조건을 만족할 때 더 큰 값은 탐색할 필요없음
    if isAllPass:
        break

if min_cost==1e9:
    print(-1)
else:
    print(min_cost)
    min_idx[min_cost].sort()
    print(*min_idx[min_cost][0], sep=' ')

• N이 최대 15이므로 완전 탐색으로 풀어도 시간초과가 발생하지 않는다.
• N개의 식품 인덱스 중 1부터 N개를 뽑는 조합을 모두 탐색하면서 해당 조합으로 조건을 만족할 수 있는지 확인한다.
• 조건을 만족한다면 해당 조합의 비용이 이전 계산에서 구한 최소 비용보다 작거나 같다면 최소 비용과 최소 비용을 구성하는 식품 인덱스인 min_cost와 min_idx를 업데이트한다.
• 그리고 특정 n개를 뽑을 때, 모든 조합이 조건을 만족한다면 그 이상의 수를 뽑는 것 또한 모두 만족한다는 뜻이므로 뽑을 개수 n개를 더 이상 탐색하지 않고 for문을 빠져나온다.
• 최소 비용을 구성하는 식품 인덱스를 구하는 과정에서 주의할 점은 해당하는 식품 인덱스가 여러 개일 경우 사전순으로 가장 앞서는 식품 인덱스를 출력해야 하기 때문에 각 최소 비용에 대한 식품 인덱스를 딕셔너리 형태로 저장해두고, 최종적으로 구해진 최소 비용에 해당하는 식품 인덱스들을 정렬해준 뒤에 가장 앞에 오는 요소를 출력해줘야 한다.