SW Expert Academy 4012. [모의 SW 역량테스트] 요리사 풀이 With Python

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH&categoryId=AWIeUtVakTMDFAVH&categoryType=CODE

SW Expert Academy

itertools 모듈의 combinations 함수를 이용하여서 절반을 뽑아서 식재료를 2가지 경우로 나누어서 각 시너지 효과를 종합하여 두 요리의 맛의 차이의 절댓값을 계속 경신하였다. 아래는 내가 해결한 코드이다.

from itertools import combinations


def solution(map1, n):
    answer = float('inf')
    sub = list(combinations(range(n), n // 2))
    for i in sub:
        sub1 = []
        r1 = 0
        sub2 = []
        r2 = 0
        for j in range(n):
            if j in i:
                sub1.append(j)
            else:
                sub2.append(j)
        for p in range(n // 2):
            for p2 in range(n // 2):
                if sub1[p] != sub1[p2]:
                    r1 += map1[sub1[p]][sub1[p2]]
                if sub2[p] != sub2[p2]:
                    r2 += map1[sub2[p]][sub2[p2]]
        sub3 = abs(r1 - r2)
        if answer > sub3:
            answer = sub3
    return answer


t = int(input())
for test in range(1, t + 1):
    n = int(input())
    map1 = [list(map(int, input().split())) for _ in range(n)]
    ans = solution(map1, n)
    print('#{} {}'.format(test, ans))