[SWEA] 4012. 모의 SW 역량테스트 - 요리사

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH

SW Expert Academy

 

설계

재료의 개수(level) 만큼 A, B에 나눠준다.

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    visit = [0]*N

    minV = 999999
    def dfs(level, A, B):
        global minV

        if level == N:
            if len(A) == len(B):     # 식재료를 모두 나누고 A와 B에 나누어진 식재료의 개수가 같은 경우
                sumA, sumB = 0, 0
                for i in range(N//2):
                    for j in range(N//2):
                        if i == j:          # 예외처리: 같은 식재료일 경우
                            continue
                        sumA += arr[A[i]][A[j]]
                        sumB += arr[B[i]][B[j]]
                minV = min(minV, abs(sumA-sumB))        # 최소값 갱신
            return
        dfs(level+1, A+[level], B)
        dfs(level+1, A, B+[level])
    dfs(0, [], [])      # level, A요리, B요리
    print(f'#{tc} {minV}')