algorithmStudy/BJ14889.py at main · KeonhoPark/algorithmStudy · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import sys

n = int(sys.stdin.readline())
data = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
flag = [0 for _ in range(n)]
start = list()
res = 1e9


def dfs(l, s):
    global res

    if l == n // 2:
        s_score = 0
        l_score = 0
        link = list()
        for i in range(n):
            if i not in start:
                link.append(i)

        for i in start:
            for j in start:
                s_score += data[i][j]

        for i in link:
            for j in link:
                l_score += data[i][j]

        res = min(res, abs(s_score - l_score))
        return
    else:
        for i in range(s, n):
            if flag[i] == 0:
                flag[i] = 1
                start.append(i)
                dfs(l + 1, i)
                flag[i] = 0
                start.pop()


dfs(0, 0)
print(res)