문제

https://www.acmicpc.net/problem/14889

나의 코드

"""

"""

from itertools import combinations
from sys import stdin
input = stdin.readline

n = int(input())
pan = [ list(map(int, input().split())) for _ in range(n) ]
num = [ x for x in range(1, n+1) ]

def skill_sum(lst): # 모든 능력치의 합을 반환해주는 함수

    sum = 0
    lst = list(combinations(lst, 2)) # 넘겨받은 리스트를 2개의 쌍으로 조합해서 능력치의 합을 더해준다.
    for i, j in lst:
        sum += (pan[i-1][j-1] + pan[j-1][i-1])

    return sum

nums = list(combinations(num, n//2)) # n=6이면 3명씩 2개의 팀으로 나누기 위해 n//2를 통해 모든 경우에 대해 조합을 해줌.
lp, rp = 0, len(nums)-1
answer = 1e9

while lp <= rp: # 조합의 첫부분과 마지막 부분을 팀으로 구하기 위해 lp, rp를 씀.

    first_teamskill = skill_sum(nums[lp])
    second_teamskill = skill_sum(nums[rp])

    answer = min(answer, abs(first_teamskill-second_teamskill)) # 능력치의 합이 최소인 경우를 구하기 위해 실행

    lp, rp = lp+1, rp-1

print(answer)
    

설명

백트래킹을 통해 모든 경우에 대해 능력치가 최소인 값을 구해주면 됨.

참고 자료