[코테] 경우의 수 고려하기 - 순열과 조합

경우의 수 문제 다른 접근법: 순열과 조합

permutation : 순열

nPr 순서를 고려하여 r개 줄 세우기

from itertools import permutations

arr = ['A', 'B', 'C']
nPr = permutations(arr, 2)
print(list(nPr))

# [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

combination : 조합

nCr 순서 상관 없이 n개 중 r개 뽑기

from itertools import combinations

arr = ['A', 'B', 'C']
nCr = combinations(arr, 2)
print(list(nCr))

# [('A', 'B'), ('A', 'C'), ('B', 'C')]

위에 재귀로 풀었던 "영양 성분 경우의 수" 문제를 조합을 사용해서 풀어보자

import sys
input = sys.stdin.readline
from itertools import combinations

n = int(input())
mp, mf, ms, mv = map(int, input().split())

ingredients = [list(map(int, input().split())) for _ in range(n)]

min_cost = int(1e9)
selected_ingredient = []

# 전체 경우의 수를 조합을 사용해서 탐색
for i in range(1, n+1):
    for comb in combinations(range(1, n+1), i):
        tp = tf = ts = tv = tc = 0
        for idx in comb:
            tp += ingredients[idx-1][0]
            tf += ingredients[idx-1][1]
            ts += ingredients[idx-1][2]
            tv += ingredients[idx-1][3]
            tc += ingredients[idx-1][4]

        if tp >= mp and tf >= mf and ts >= ms and tv >= mv:
            if min_cost > tc:
                min_cost = tc
                selected_ingredient = comb

            # 같은 비용의 집합이 하나 이상인 경우 사전 순으로 빠른 것 출력
            if min_cost == tc:
                selected_ingredient = sorted((selected_ingredient, comb))[0] # 기존 선택된 집합과 현재 집합을 하나의 튜플로 묶어 정렬 후 빠른 것 선택

if min_cost != int(1e9):
    print(min_cost)
    print(*sorted(selected_ingredient))
else:
    print(-1)