14889번 - 스타트와 링크(Python)

풀이

백트래킹을 이용해 나눌 수 있는 팀의 경우의 수를 모두 구한다.

 

우선, status[i][j]에 status[j][i]를 더했다. 따라서 status[i][j]는 i와 j가 팀이 되었을 때 더해지는 능력치의 합이 되었다.(i < j)

 

이후에 스타트 팀에 0을 고정한 상태로, 스타트 팀에 들어갈 N//2 - 1 명을 백트래킹을 이용해 배정한다.

(0이 링크 팀에 들어가는 경우는 스타트 팀에 들어가는 것과 대칭되므로 스타트팀에 속하는 경우만 계산한다.)

이후에 스타트 팀에 속하지 않은 N//2 명을 링크 팀에 배정한 후 각 팀의 점수를 구해 두 팀의 점수차의 절댓값을 ans에 넣는다.

백트래킹이 끝난 후 ans의 최솟값을 정답으로 출력한다.

코드

N = int(input())

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

for i in range(N-1):
    for j in range(i+1, N):
        status[i][j] += status[j][i]

start = [0]
ans = []
visited = [False for _ in range(N)]


def dfs(first):
    if len(start) == N//2:
        link = []
        for i in range(N):
            if i not in start:
                link.append(i)
        score_start = 0
        score_link = 0

        for i in range(N//2):
            for j in range(i+1, N//2):
                score_start += status[start[i]][start[j]]
                score_link += status[link[i]][link[j]]
        ans.append(abs(score_start-score_link))
        return

    for i in range(first+1, N):
        if not visited[i]:
            start.append(i)
            visited[i] = True
            dfs(i)
            start.pop()
            visited[i] = False


dfs(0)
print(min(ans))