[백준] 14889번 스타트와 링크 (파이썬, 완전탐색)

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

from collections import deque
from itertools import combinations
import math
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
p=[i for i in range(n)]

allcase=combinations(p,n//2)
ans=math.inf
def check(start):
    global ans
    link=[]
    for i in range(n):
        if i not in start:
            link.append(i)
    sum,sum2=0,0
    for i in range(n//2):
        for j in range(n//2):
            if i==j: continue
            sum+=a[start[i]][start[j]]
            sum2+=a[link[i]][link[j]]
    if ans>abs(sum-sum2):
        ans=abs(sum-sum2)


for case in allcase:
    check(list(case))

print(ans)