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

범위가 작아 조합으로 풀었다. check 함수 내의 반복문에서 실수가 있어서 시간이 좀 걸렸다.

import sys
from itertools import combinations
import math
 
def check(k,list):
 
    answer = 0
 
    for i in range(0,len(list)-1):
        for j in range(i+1,len(list)):
 
            answer += k[list[i]][list[j]]
            answer += k[list[j]][list[i]]
 
    return answer
 
 
 
 
num =int(input())
 
k = [ ]
 
for i in range(num):
    k.append(list(map(int,sys.stdin.readline().rstrip().split(" "))))
 
 
member = [ ]
 
for i in range(num):
    member.append(i)
 
all_sum = 0
 
for i in range(0,len(k)):
    all_sum += sum(k[i])
 
 
# 팀 나누기
 
first = list(combinations(member,int(num/2)))
 
answer = [ ]
 
for i in range(0,len(first)):
 
 
    temp = list(first[i])
 
    temp2 = [ ]
 
    for q in member:
        if q not in temp:
            temp2.append(q)
 
 
    temp_sum = check(k,temp)
 
    temp_sum2 = check(k,temp2)
 
 
 
 
    answer.append(int(math.fabs(temp_sum-temp_sum2)))
 
 
print(min(answer))