[백준 14889번] 스타트와 링크 (파이썬/python)

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

14889번: 스타트와 링크

 

모든 조합으로 팀을 정해주었다!

 

나는 조합을 만들때 스타트팀만 만들었다!

스타트팀에는 무조건 0번째 선수가 들어가있게 구성했다

이래야지 링크팀에는 무조건 0번쨰 선수가 없기 때문에

 

모든 조합을 구하는것이 아닌! 딱 모든 조합의 반절만 구할 수 있다!

 

 

import sys
from itertools import combinations
 
input = sys.stdin.readline
n = int(input())
arr = []
p_list = [0]
 
min_point = 100000000
visit = [0] * n
 
 
def score(start_list):
    s_point = 0
    l_point = 0
    link_list = [i for i in range(n) if i not in start_list]
 
    start_combi = list(combinations(start_list, 2))
    link_combi = list(combinations(link_list, 2))
 
    for s, l in zip(start_combi, link_combi):
        s_point += arr[s[0]][s[1]]
        s_point += arr[s[1]][s[0]]
        l_point += arr[l[0]][l[1]]
        l_point += arr[l[1]][l[0]]
    # print(abs(s_point - l_point))
    return abs(s_point - l_point)
 
 
def dfs(cnt, x):
    global p_list, min_point
    if cnt == (n // 2) - 1:
        result = score(p_list)
        if result < min_point:
            min_point = result
        return
 
    for i in range(x, n):
        if visit[i] == 1:
            continue
        visit[i] = 1
        p_list.append(i)
        dfs(cnt + 1, i + 1)
        p_list.pop()
        visit[i] = 0
 
 
for i in range(n):
    li = list(map(int, input().split()))
    arr.append(li)
 
dfs(0, 1)
 
print(min_point)