[BOJ] 19942 다이어트(python)

문제

식재료 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이 되므로, 앞의 방법보다는 더 나은 선택이 된다.

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

입력

첫 줄에 식재료의 개수 $N$이 주어진다.

다음 줄에는 단백질, 지방, 탄수화물, 비타민의 최소 영양성분을 나타내는 정수 $mp$, $mf$, $ms$, $mv$가 주어진다.

이어지는 $N$개의 각 줄에는 $i$번째 식재료의 단백질, 지방, 탄수화물, 비타민과 가격이 5개의 정수 $p_i$, $f_i$, $s_i$, $v_i$, $c_i$와 같이 주어진다. 식재료의 번호는 1부터 시작한다.

출력

첫 번째 줄에 최소 비용을 출력하고, 두 번째 줄에 조건을 만족하는 최소 비용 식재료의 번호를 공백으로 구분해 오름차순으로 한 줄에 출력한다. 같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력한다.

조건을 만족하는 답이 없다면 -1을 출력하고, 둘째 줄에 아무것도 출력하지 않는다.

제한

• $3 \le N \le 15$ 
• $0 \le mp, mf, ms, mv \le 500$ 
•  $mp + mf + ms + mv > 0$ 
• $0 \le p_i, f_i, s_i, v_i, c_i \le 500$ 

풀이

해봤자 식재료 갯수가 최대 15개라서 그냥 전부 다 탐색하는 방향으로 정했다.
itertools.combinations를 이용해서 간단하게 모든 경우의 수를 사용했고, operator.add로 list의 element-wise 연산을 쉽게 했다.

사전순으로 빠른 것을 출력한다길래 어떤 방식으로 해야할지 계속 고민하다가 찾은 방법이
int를 str으로 바꾸고 join으로 합쳐서 사전순 비교를 하는 방법이였다.

이번 문제를 풀면서 operator.add와 ''.join()방법을 겨우 고안해내서 난 아직 멀었구나 싶었다.

그리고 제대로 풀었다고 생각했는데 계속 틀렸다길래 뭐가 문제인지 한참을 생각하다가 조건을 똑바로 만족하지 못했다는 것을 깨달았다.
원래 min_value를 501로 설정했는데, 이게 총 합이 500을 안넘는다는 것이 아니라 각각의 수치들이 500을 안넘는 것이기 때문에 15개 재료를 다 쓰고 각 재료값이 500이라면 7500이 돼서 틀린 것이였다.
그래서 그냥 널널하게 1000000으로 설정했다.

import sys
from itertools import combinations
from operator import add

num_ingreds = int(sys.stdin.readline())
min_nutr = list(map(int, sys.stdin.readline().split()))

ingredients = []
for _ in range(num_ingreds):
    ingredients.append(list(map(int, sys.stdin.readline().split())))

min_value = 1000000  # 어지간하면 널널하게 설정하는게 좋은 것 같다.

for i in range(1, num_ingreds+1):
	# combinations로 모든 경우의 수에 대해 탐색
    for combi in list(combinations(range(num_ingreds), i)):
        tmp = [0]*5
        
        # element-wise 연산 쉽게 하기 위한 부분
        for c in combi:
            tmp = list(map(add, tmp, ingredients[c]))

        if tmp[0] >= min_nutr[0] and tmp[1] >= min_nutr[1] and tmp[2] >= min_nutr[2] and tmp[3] >= min_nutr[3] and tmp[4]<=min_value:
            # .join()으로 사전순서 비교
            if tmp[4] == min_value:
                if ''.join(map(str, combi)) > ''.join(map(str, min_idxs)):
                    continue
            min_value = tmp[4]
            min_idxs = combi
            
if min_value == 1000000:
    print(-1)
else:
    print(min_value)
    # 인덱스 0부터 시작해서 각 인덱스에 1더해서 출력
    print(' '.join(map(str,[i+1 for i in min_idxs])))