[파이썬] [구현] 백준 14889 스타트와 링크

문제

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

14889번: 스타트와 링크

코드

import sys
from itertools import combinations

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

com=list(combinations(range(n),n//2))

result=sys.maxsize
for start in com:
    # 조합으로 start팀을 구한후, 차집합을 통해 link팀 구함
    link=set(range(n)).difference(set(start))

    teamStart=0
    teamLink=0
    for a,b in list(combinations(start,2)):
        teamStart+=array[a][b]
        teamStart+=array[b][a]
    for a,b in list(combinations(link,2)):
        teamLink+=array[a][b]
        teamLink+=array[b][a]
    result=min(result,abs(teamStart-teamLink))

print(result)