문제 설명

문제 해결 과정

1. 팀을 나눈다.
2. 각 팀의 능력치 합계를 구한다.
3. 2번의 차와 최소값을 비교하여 최소값을 찾아간다.

1. 팀을 나눈다.

팀을 반으로 나누는 거니까 nCn/2를 하면 된다.

단, 겹치는 경우를 제거해야 시간을 줄일 수 있다. (안 해도 시간 초과가 뜨는 지 안 뜨는지는 잘 모르겠다.)

맨 앞자리가 1인 경우만 DFS를 끝까지 돌면 된다. 왜?

ex)

같은 색깔을 친 애들끼리 반대팀이다. 1(꼭 1이 아니어도 특정 기준) 기준으로 1이 1팀에 속하든, 2팀에 속하든 같은 경우로 치기 때문이다.

반대팀을 구하는건 파이썬의 내장 기능인 세트 연산을 적절히 이용했다.

2. 각 팀의 능력치 합계를 구한다.

n/2C2 하면 된다.

ex)3C2 -> (1, 2), (1, 3), (2, 3)

앞뒷자리만 바꿔서 계산하면 Sij와 Sji 모두 구할 수 있다.

3. 2번의 차와 최소값을 비교하여 최소값을 찾아간다.

이하 생략.

소스코드

import sys

minv = sys.maxsize

def dfs(x, team1):
    global minv
    if x == n//2+1: #여기서 dfs 종료. team1과 team2 분리
        sum1 = 0
        sum2 = 0
        team2 = list(set([i for i in range(1, n+1)]) - set(team1))
        for i in range(n//2):
            for j in range(i, n//2):
                sum1 += arr[team1[i]-1][team1[j]-1] + arr[team1[j]-1][team1[i]-1]
                sum2 += arr[team2[i]-1][team2[j]-1] + arr[team2[j]-1][team2[i]-1]
        
        minv = min(minv, abs(sum1-sum2))
        return

    for i in range(team1[-1] if team1 else 1, n+1):
        if i not in team1: dfs(x+1, team1+[i])
        if x == 1: break

n = int(input())
arr = []

for i in range(n):
    arr.append(list(map(int, input().split())))

dfs(1, [])

print(minv)