✅문제 요약

1. 스타트팀 링크팀으로 나누어 경기를 진행한다.
2. n명의 팀원들이 있고, i번 팀원과 j번 팀원이 같은팀일때 시너지가 나타난다
3. 시너지는 nxn격자로 주어지고 S[i][j]와 S[j][i]는 다르고 두개의 합이 i번 j번 선수가 같은팀이 됐을 때 더해지는 시너지다
4. 각 팀의 시너지 차이가 최소가 되는 값을 출력하라

✅문제 풀이

모든 경우를 탐색해야 알 수 있는 브루트포스 문제다.
즉 4명이 팀일 때 팀은 12/34 또는 13/24 또는 14/23 으로 나뉠 수 있다.
모든 팀의 조합을 구하고 각 조합에서 시너지 값을 구해 차이의 최솟값을 도출한다.

def perm(n):
    global min_v
	
    # 팀원을 모두 나눴다면
    if n == N//2:
        # 각 팀 능력치 계산
        sv,lv = 0, 0

        for i in range(N):
            if i in start:continue
            # 스타트 팀에 없는 멤버 링크에 추가
            link.append(i)

        for i in range(N//2-1):
            for j in range(i+1, N//2):
                # 각 팀 시너지 값 계산
                sv += arr[start[i]][start[j]] + arr[start[j]][start[i]]
                lv += arr[link[i]][link[j]] + arr[link[j]][link[i]]

        # 시너지 최솟값 갱신
        min_v = min(min_v, abs(sv-lv))
        link.clear()
        return

    for i in range(N):
        # 했던 번호 가지치기
        if i in start:continue
        # 이전에 0번을 했다면 1번 부터 하기위한 가지치기
        if len(start) > 0 and start[len(start)-1] > i:continue
        start.append(i)
        perm(n + 1)
        start.pop()


N = int(input())    # 축구하러 모인 인원
arr = [list(map(int, input().split())) for _ in range(N)]   # 능력치 배열 arr[i][i] = 0


start = []			# 스타트 팀 멤버 번호
link = []			# 링크 팀 멤버 번호
min_v = float('Inf')# 시너지 최솟값

perm(0)
print(min_v)