1. 문제

14889번

2. 풀이

# 입력
N = int(input())
depth = N // 2
S = []

for _ in range(N):
    S.append(list(map(int, input().split())))

# 저장 공간 정의
team = [] # 팀 분류 공간 - S_ij의 i와 j가 될 후보들이 저장된다.

index_ = []
# team 공간의 index이며 team 공간에서 dfs 방식으로 2개씩 뽑을 때 사용
# 예를 들어, team = [0, 3, 4, 5] 이면,
# index_는 [0,1], [0,2] ... 와 같은 식으로
# index의 tree를 만든다.

temp = []
# team 공간에 저장된 i, j를 가지고
# S에서 S_ij + S_ji를 구하여 임시 저장

sum_ = [] # temp에 저장된 값들을 모두 더한다.

# 팀이 분류 된 후 팀 내에서 두개의 index를 선택하여 합을 구한다.
# Depth가 2인 Tree를 DFS 방식으로 탐색
def dfs_S(jter, len_r):
    global temp
    if len(index_) == 2:
    	# index_에는 team에서 2개의 숫자를 고르기 위한 
        # indexing number 가 저장되어 있다.
        temp.append(S[team[index_[0]]][team[index_[1]]] +\
             S[team[index_[1]]][team[index_[0]]])
        return
    for j in range(jter, len_r):
        index_.append(j)
        dfs_S(j + 1, len_r)
        index_.pop()

# N개의 팀 후보를 N/2로 분류
# 한쪽 팀을 DFS방식으로 분류
def dfs(iter):
    global temp
    if len(team) == depth:
    	# N / 2에 도달하면 팀 내에서 2개의 indexing number를 탐색
        dfs_S(0, len(team))
        sum_.append(sum(temp)) # S_ij + S_ji의 값을 모두 더해 팀의 총 능력치 계싼
        temp = []
        return
    for i in range(iter, N):
        team.append(i)
        dfs(i + 1)
        team.pop()

dfs(0)

answer = []
for i in range(len(sum_)//2):
	# 분류 가능한 팀의 경우의 수가 x일 때,
    # 0번째 분류와 x - 0 번째 분류는 동치이다.
    answer.append(max(sum_[i], sum_[len(sum_) - i - 1]) -\
          min(sum_[i], sum_[len(sum_) - i - 1]))

print(min(answer))