[BOJ] 14889번 스타트와 링크 (Python)

import sys
from itertools import combinations,permutations

input = sys.stdin.readline

N = int(input())
powers = [list(map(int,input().split())) for _ in range(N)]

person_nums = list(range(N))
start_team_candidate = list(combinations(person_nums,N//2))

ans = sys.maxsize
for start_team in start_team_candidate:
  link_team = [x for x in person_nums if x not in start_team]
  start_sum = sum(powers[i][j] for i,j in list(permutations(start_team,2)))
  link_sum = sum(powers[i][j] for i,j in list(permutations(link_team,2)))
  power_gap = abs(start_sum-link_sum)
  
  if ans > power_gap:
    ans = power_gap

print(ans)