BOJ 14889번: 스타트와 링크

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

14889번: 스타트와 링크

두 팀으로 나누는 걸 어떻게 구현해야 할 지 감이 잘 오지 않았다. 

1부터 N명의 선수가 있을 때, 그 선수가 a팀에 들어가는 경우와 b팀에 들어가는 경우 두 가지 이므로,, 그걸 이용해서 백트래킹으로 풀 수 있을 것이라 생각했다. 그런데 파이썬은 시간초과가 나왔고, pypy는 15프로 정도에서 틀렸다고 계속 떠서.. 일단 파이썬 조합 라이브러리를 이용해서 풀었다. 

처음에는 심지어 N은 짝수이고 N/2명으로 나눈다는 조건은 보지도 않고 풀어서 더 헤맸었다. 문제 좀 제대로 읽자.

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

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

total = [i for i in range(N)]
cb = list(combinations(total, N//2))
ans = 1000000

for c in cb:
    start = set(c)
    link = list(set(total) - start)
    start = list(start)

    a, b = 0, 0

    for i in range(N//2):
        for j in range(i+1, N//2):
            a += arr[start[i]][start[j]] + arr[start[j]][start[i]]
            b += arr[link[i]][link[j]] + arr[link[j]][link[i]]
    ans = min(ans, abs(a-b))

print(ans)