BOJ 14889 스타트와 링크 (Python)

문제풀이

풀이과정

• start팀과 link팀 총 2개의 팀으로 나누어지기 때문에 하나의 팀을 구성하면 다른 한 팀의 팀원도 정해진다. 조합 라이브러리를 사용하면 쉽게 풀리는 문제

Code

import sys
from itertools import combinations

n = int(input())
result = sys.maxsize

datas = []

for _ in range(n):
    datas.append(list(map(int,input().split())))

temp_list = [i for i in range(n)]
comb_list = list(combinations(temp_list, n//2))

for comb in comb_list:
    team_start = comb
    team_link = tuple(set(temp_list) - set(comb))
    start = 0
    link = 0
    
    for i,j in combinations(team_start, 2):
        start += datas[i][j] + datas[j][i]

    for k,l in combinations(team_link, 2):
        link += datas[k][l] + datas[l][k]
        
    result = min(abs(start - link), result)
    
print(result)