Baekjoon-14889-스타트와 링크

N = int(input())

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

min_score = int(1e5)
def dfs(depth, team1, team2, score_diff):
    global min_score
    if depth == N//2:
        if min_score > abs(score_diff):
            min_score = abs(score_diff)
        return

    start_idx = 0 if len(team1)==0 else team1[-1]+1
    for new_team1 in range(start_idx, N//2+depth+1):
        add_team1 = [new_team1]
        add_team2 = [j for j in range(start_idx,max(0,new_team1))]
        if depth == N//2-1:
            add_team2 += [j for j in range(new_team1+1,N)]
        add_score = 0
        for t in team1:
            add_score += S[t][new_team1] + S[new_team1][t]
        for j, at in enumerate(add_team2):
            for t in team2+add_team2[:j]:
                add_score -= (S[t][at] + S[at][t])
        dfs(depth+1, team1+add_team1, team2+add_team2, score_diff+add_score)

dfs(0,[],[],0)
print(min_score)