[SWEA][Python] 4012 요리사

조합을 dfs로 짜고, 조합에 속한 요소와 속하지 못한 요소간 차이를 비교. 삼성기출 스타트와 링크. 웰노운

 

def choose_parts(cur_node, cnt):
    global min_gap
    if cnt == N // 2:
        S1, S2 = 0, 0
        for i in range(N - 1):
            for j in range(i + 1, N):
                if check[i] and check[j]:
                    S1 += S[i][j] + S[j][i]
                elif not check[i] and not check[j]:
                    S2 += S[i][j] + S[j][i]
        min_gap = min(min_gap, abs(S1 - S2))
    for next_node in range(cur_node, N):
        if not check[next_node]:
            check[next_node] = True
            choose_parts(next_node + 1, cnt + 1)
            check[next_node] = False


for test in range(1, int(input()) + 1):
    N = int(input())
    S = [list(map(int, input().split())) for _ in range(N)]
    check = [False] * N
    min_gap = float('inf')
    choose_parts(0, 0)
    print(f'#{test} {min_gap}')