[Python] 백준 <14889-스타트와 링크>

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

 

import sys
from itertools import combinations
input = sys.stdin.readline

N = int(input())
li = list()

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

person = list(range(N))
two_li = list(combinations(person, 2))
    
dic = dict()

# 두명 경우의 수 시너지 합 모두 구하기
for a, b in two_li:
    dic[f"{a},{b}"] = li[a][b] + li[b][a]

one_team = N//2
team = list(combinations(person, one_team))

#팀프로 나올수 있는 모든 경우의 수 시너지 구하기
team_dic = dict()
for i in team:
    one_team_two = list(combinations(i, 2))
    for a, b in one_team_two:
        team_dic[i] = team_dic.get(i, 0) + dic[f"{a},{b}"]

#상대팀과의 차 구하고 리스트에 저장
dap = list()
for k, v in team_dic.items():
    dap.append(abs(v-team_dic[tuple(set(person) - set(k))]))

#제일 작은 차가 정답
print(min(dap))