[코딩인터뷰] 백준 14889번

백준 14889번

import itertools

n = int(input())
score_board = []
for _ in range(n):
    score_board.append(list(map(lambda i:int(i), input().split())))

team = range(n)
min_dist = 10**8
for selected in itertools.combinations(team, n//2):
    start_team = selected
    link_team = []

    for k in range(n):
        if k not in selected:
            link_team.append(k)

    start_team_score = 0
    link_team_score = 0
    for m in itertools.combinations(start_team, 2):
        start_team_score += score_board[m[0]][m[1]] + score_board[m[1]][m[0]]

    for m in itertools.combinations(link_team, 2):
        link_team_score += score_board[m[0]][m[1]] + score_board[m[1]][m[0]]

    if abs(start_team_score - link_team_score) < min_dist:
        min_dist = abs(start_team_score - link_team_score)

print(min_dist)