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

---

1. 코드

N = int(input())
lst = list(range(1, N+1))

def score_calculate(k):
    score = 0
    for i in range(N//2):
        for j in range(i+1, N//2):
            score += graph[k[i]-1][k[j]-1] + graph[k[j]-1][k[i]-1]
    return score

def check(k):
    global ans
    start = set(k)
    link = set(lst)-start
    start_score = score_calculate(list(start))
    link_score = score_calculate(list(link))
    ans = min(ans, abs(start_score-link_score))

def dfs(cnt, idx, path):
    if cnt==(N//2):
        check(path)
        return
    for i in range(idx, len(lst)):
        dfs(cnt+1, i+1, path + [lst[i]])


ans = 9999
graph = [list(map(int, input().rstrip().split())) for _ in range(N)]
dfs(0, 0, [])
print(ans)

---

2. 후기

실제 시험이라면 조합 라이브러리를 사용하는 편이 좋을듯