능력치 차이가 최소인 두 팀

면접 대비

시간 제한2초메모리 제한512 MB

요약

N명을 두 팀으로 나눌 때 각 팀의 모든 순서쌍 능력 합의 차이를 최소로 만들고 그 최솟값을 출력한다.

난이도: 보통10점 중 6점
유형: 비트 연산, 완전 탐색, 배열, 조합론
정답자: 아직 제출이 없습니다

문제

$N$ 명이 모여 축구를 하려고 한다. 이 사람들을 스타트 팀과 링크 팀으로 나눈다. 두 팀의 인원수는 같지 않아도 되지만, 각 팀에 적어도 한 명은 있어야 한다.

사람에게 1번부터 $N$ 번까지 번호를 붙이고 능력치 표 $S$ 를 조사했다. $S_{ij}$ 는 $i$ 번 사람과 $j$ 번 사람이 같은 팀일 때 그 팀에 더해지는 능력치다. 팀의 능력치는 그 팀에 속한 서로 다른 두 사람의 모든 순서쌍에 대한 능력치를 더한 값이다. $S_{ij}$ 와 $S_{ji}$ 는 값이 다를 수 있고, $i$ 번 사람과 $j$ 번 사람이 같은 팀이면 $S_{ij}$ 와 $S_{ji}$ 가 모두 그 팀의 능력치에 더해진다.

$N$ 이 4이고 $S$ 가 다음과 같은 경우를 보자.

$S_{ij}$	$j=1$	$j=2$	$j=3$	$j=4$
$i=1$	0	1	2	3
$i=2$	4	0	5	6
$i=3$	7	1	0	2
$i=4$	3	4	5	0

1번과 2번이 스타트 팀, 3번과 4번이 링크 팀이면 스타트 팀의 능력치는 $S_{12} + S_{21} = 1 + 4 = 5$ 이고, 링크 팀의 능력치는 $S_{34} + S_{43} = 2 + 5 = 7$ 이다. 1번과 3번이 스타트 팀, 2번과 4번이 링크 팀이면 스타트 팀은 $S_{13} + S_{31} = 2 + 7 = 9$ , 링크 팀은 $S_{24} + S_{42} = 6 + 4 = 10$ 이다.

두 팀의 능력치 차이를 가장 작게 만드는 것이 목표다. 위 표에서는 1번과 4번이 스타트 팀, 2번과 3번이 링크 팀일 때 두 팀의 능력치가 모두 6이 되어 차이가 0이고, 이보다 작게 만들 수는 없다.

입력

첫째 줄에 $N$ 이 주어진다. ( $4 \le N \le 20$ )

둘째 줄부터 $N$ 개의 줄에 걸쳐 $S$ 가 주어진다. 각 줄은 $N$ 개의 수로 이루어지고, $i$ 번째 줄의 $j$ 번째 수가 $S_{ij}$ 다. $S_{ii}$ 는 항상 0이고, 나머지 $S_{ij}$ 는 1 이상 100 이하의 정수다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치 차이의 최솟값을 출력한다.

예제4

예제 1
입력
```
4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0
```
예상 출력
```
0
```

예제 2

입력

6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0

예상 출력

예제 3

입력

8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0

예상 출력

예제 4

입력

예상 출력