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

14889번: 스타트와 링크

---

조합을 쓰자.

 

1. 후보 candidate를 N명 생성한다.
2. 조합을 통해 스타트팀을 구하고 나머지를 링크팀으로 정한다.
3. 스타트팀 점수는 더하고 링크팀 점수는 뺀다
4. 절대값이 가장 작은 값을 출력한다.

 

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

N = int(input())
arr = []
for _ in range(N):
    _input = list(map(int, input().split()))
    arr.append(_input)

candidate = [i for i in range(N)]
result = sys.maxsize
for comb in combinations(candidate, N//2):
    start = set(comb)
    link = set(candidate) - start
    start = list(start)
    link = list(link)

    score = 0
    for i in range(1, N//2):
        for j in range(i):
            score += arr[start[i]][start[j]] + arr[start[j]][start[i]]
            score -= arr[link[i]][link[j]] + arr[link[j]][link[i]]
    result = min(abs(score), result)

print(result)