[Python] 4012. 요리사

1. 조합을 직접 구현하여 해결한 풀이

# 조합 구하기
def combination(idx, cnt, a_arr):
    if cnt == n//2: # 식재료 다 골랐다면
        cal_diff(a_arr) # 두 음식의 맛 차이 구하러 고고
        return
 
    for i in range(idx, n):
        combination(i+1, cnt+1, a_arr+[i])  # 다음 번호 구해 [0, 1, 2] -> [0, 1, 3] -> [0, 1, 4]
 
 
# a, b 음식 맛 차이 구하기
def cal_diff(a_arr):
    global answer
 
    a, b = 0, 0
    b_arr = [i for i in range(n) if i not in a_arr] # a 음식에서 선택하지 않은 식재료 선택
    for i in range(n//2-1):
        for j in range(i+1, n//2):
            a += synergy[a_arr[i]][a_arr[j]] + synergy[a_arr[j]][a_arr[i]]  # a 음식의 맛 더하기
            b += synergy[b_arr[i]][b_arr[j]] + synergy[b_arr[j]][b_arr[i]]  # b 음식의 맛 더하기
 
    answer = min(answer, abs(a-b))  # 최소값으로 갱신
 
 
tc = int(input())
for idx in range(1, tc+1):
    n = int(input())    # 식재료 개수
    synergy = [list(map(int, input().split())) for _ in range(n)]   # 음식들의 시너지
 
    answer = 9999999999
    combination(0, 0, [])
    print('#{} {}'.format(idx, answer))

 

2. itertools의 combinations 사용한 풀이 

from itertools import combinations
 
 
tc = int(input())
for idx in range(1, tc+1):
    n = int(input())    # 식재료 개수
    synergy = [list(map(int, input().split())) for _ in range(n)]   # 음식들의 시너지
 
    answer = 9999999999
    for a_arr in combinations(range(n), n//2):  # a 음식 고를 식재료 선택
        b_arr = [i for i in range(n) if i not in a_arr]  # a 음식에서 선택하지 않은 식재료 선택
        a, b = 0, 0
        for i in range(n // 2 - 1):
            for j in range(i + 1, n // 2):
                a += synergy[a_arr[i]][a_arr[j]] + synergy[a_arr[j]][a_arr[i]]  # a 음식의 맛 더하기
                b += synergy[b_arr[i]][b_arr[j]] + synergy[b_arr[j]][b_arr[i]]  # b 음식의 맛 더하기
 
        answer = min(answer, abs(a - b))  # 최소값으로 갱신
 
    print('#{} {}'.format(idx, answer))

 

3. itertools의 combinations, permutations 사용한 풀이 

from itertools import permutations, combinations
 
 
tc = int(input())
for idx in range(1, tc+1):
    n = int(input())    # 식재료 개수
    synergy = [list(map(int, input().split())) for _ in range(n)]   # 음식들의 시너지
 
    answer = 9999999999
    for a_arr in combinations(range(n), n//2):  # a 음식 고를 식재료 선택
        b_arr = [i for i in range(n) if i not in a_arr]  # a 음식에서 선택하지 않은 식재료 선택
        a, b = 0, 0
        for i, j in permutations(a_arr, 2):
            a += synergy[i][j]   # a 음식의 맛 더하기
 
        for i, j in permutations(b_arr, 2):
            b += synergy[i][j]   # b 음식의 맛 더하기
 
        answer = min(answer, abs(a - b))  # 최소값으로 갱신
 
    print('#{} {}'.format(idx, answer))