[백준][Python][14889][브루트포스] 스타트와 링크

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

14889번: 스타트와 링크

브루트 포스 문제다.

 

모든 팀 조합을 구하고, 그 조합들에서 차이가 가장 안나는 조합으로 최솟값을 구한다.

 

문제의 N이 작으므로 조합을 통해 다 구해보자.

 

for c in combinations(orig,n//2) 은 0~n-1 까지의 모든 숫자를 반으로 나눈다.

그 다음 각각 나눠진 팀을 c, news 라 한다. 이는 Set 연산으로 구할 수 있다.

 

그 후 각각의 c에 대해 score연산을 통해 최솟값을 구한다.

 

score 연산은, 문제에 나와있는 그대로, 각 조합에 대해 점수를 더해서 반환한다.

import sys
from itertools import permutations, combinations
n = int(sys.stdin.readline())
d = []

orig = set([i for i in range(n)])

minval = 210000000000
for i in range(n):
    d.append([int(i) for i in sys.stdin.readline().split()])

def score(l):
    ret = 0
    for c in combinations(l,2):
        ret+=d[c[0]][c[1]]+ d[c[1]][c[0]]

    return ret

for c in combinations(orig,n//2):
    news = orig-set(c)
    minval = min(abs(score(c)-score(news)), minval)


print(minval)