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

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

from itertools import combinations

N=int(input())
l=[x for x in range(N)]
S=[]
result=int(1e9)

for i in range(N):
    S.append(list(map(int, input().split())))

comb=list(combinations(l,N//2))
length=len(comb)//2

for i in range(length):
    start=0
    link=0
    for j in range(N//2):
        for k in range(j+1, N//2):
            start+=(S[comb[i][j]][comb[i][k]]+S[comb[i][k]][comb[i][j]])
    temp=[x for x in l if x not in comb[i]]
    for j in range(N//2):
        for k in range(j+1, N//2):
            link+=(S[temp[j]][temp[k]]+S[temp[k]][temp[j]])
    result=min(result, abs(start-link))

print(result)

 

브루트 포스 알고리즘으로 하나씩 케이스를 계산하여 최소값을 찾는 경우로 했다.

이때 각 경우의 수를 구할 땐 조합을 구하는 라이브러리인 itertools-combinations 를 이용하였다.