#14889

N = int(input())
Nlist = [i for i in range(0,N)]

from itertools import combinations  

inputMap = []
for i in range(N):
    inputMap.append(list(map(int, input().split())))

minVal = 1e9

# startTeam = []
# linkTeam = []

cnt = 0

# Nlist = [i for i in range(1,N+1)]
# print(Nlist)

totalList = []
combiList = list(combinations(Nlist, int(N/2)))

for oneVal in combiList:
    startTeam = list(oneVal)
    linkTeam = [x for x in Nlist if x not in startTeam]
    totalList.append([startTeam, linkTeam])

def funcProcess():
    global minVal

    for Team in totalList:
        startTeam = Team[0]
        linkTeam = Team[1]
        sumStart = 0
        sumLink = 0
        # print("startTeam = ", startTeam)
        # print("linkTeam = ", linkTeam)


        # startTeam =  [0, 1, 4]
        for i in range(0, len(startTeam)):
            # print("i = ", i)
            for j in range(i+1, len(startTeam)):
                # print("i = ", i , " j = ", j, " startTeam[i] = ", startTeam[i], " startTeam[j] = ", startTeam[j]) 
                sumStart += inputMap[startTeam[i]][startTeam[j]] + inputMap[startTeam[j]][startTeam[i]]
        # print("sumStart = ", sumStart)
        # startTeam 합 구하기
        
        # linkTeam = [2,3,5]
        for i in range(len(linkTeam)):
            for j in range(i+1, len(linkTeam)):
                sumLink += inputMap[linkTeam[i]][linkTeam[j]] + inputMap[linkTeam[j]][linkTeam[i]]
        # print("sumLink = ", sumLink)
        # linkTeam 합 구하기
        
        
        minVal = min(minVal, abs(sumStart-sumLink))
        # print("minVal = ", minVal)
        # 최소값 구하기
        # print("minVal = ", minVal)

funcProcess()
print(minVal)

주용이가 가르쳐 준 꿀팁, 이전에 알고리즘 풀면서 익혀뒀던 유용한 팁 전부 활용

1. minVal = 1e9
   어찌보면 졸라 당연하지만? 이걸 몰랐다..
2. 조합, 중복 조합, 순열, 중복 순열 => itertools
   라이브러리를 쓸 줄 몰라서 1시간 삽질했다...
3. linkTeam 구할 때 1~6까지에서 startTeam 에 있는거 빼주고 나머지를 linkTeam에 넣어주면 된다 => [x for x in Nlist if x not in startTeam]

조합으로 팀이 나눠졌고, 그 상황에서 startTeam이 만약 [0, 1, 4] , linkTeam이 만약 [2, 3, 5] 라고 했을 때 2중 for loop 를 돌면서?
inputMap 의 [0,1] + [1,0] + [0,4] + [4,0] + [1,4] + [4,1] 의 값을 sumStart 로 두고 똑같이 sumLink 를 구한다.

그리고 둘의 차이를 minVal 과 비교하여 모든 경우에서 최소값을 구한다.

이 때 2중 for loop 에서 index계산을 잘못해서 또 30분 삽질했다.

결론은 간단했다. for i in (3,3) 이면 아무 일도 벌어지지 않는다.

이 문제의 핵심은

N = int(input())
Nlist = [i for i in range(0,N)]

from itertools import combinations  

inputMap = []
for i in range(N):
    inputMap.append(list(map(int, input().split())))

minVal = 1e9

# startTeam = []
# linkTeam = []

cnt = 0

# Nlist = [i for i in range(1,N+1)]
# print(Nlist)

totalList = []
combiList = list(combinations(Nlist, int(N/2)))

이 부분이었다. 다음에 비슷한 문제가 나온다면 또 쓸 수 있게 확실하게 이해하고 넘어가자.