[백준] 스타트와링크 python (201004)

1. 문제 

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

 

2. 풀이 

import sys
from itertools import permutations, combinations

num = int(sys.stdin.readline())

skill_matrix = []
for idx in range(num):
    skill_matrix.append(list(map(int, sys.stdin.readline().split())))

players = list(range(num))
team_list = sorted(list(set(combinations(players,int(num/2)))))

total_gap = []
team_list_len = len(team_list)
min_gap = 10000000
for idx in range(int(team_list_len//2)) : # 절반만 탐색

    # get now team combi score
    now_combi = 0
    now_team = team_list[idx]
    for one_p in now_team:
        for other_p in now_team:
            now_combi += skill_matrix[one_p][other_p]

    # get opposite team combi score
    opp_combi = 0
    now_opp_team = team_list[team_list_len - idx - 1] # opposite team
    for one_p in now_opp_team:
        for other_p in now_opp_team:
            opp_combi += skill_matrix[one_p][other_p]

    gap = abs(now_combi - opp_combi)
    min_gap = min(min_gap, gap)


print(min_gap)