문제

https://www.acmicpc.net/problem/15661

나의 코드

"""

"""

from sys import stdin
input = stdin.readline

n = int(input())
visited = [False] * n
pan = [ list(map(int, input().split())) for _ in range(n) ]
answer = 1e9

def dfs(depth, idx):
    global answer

    if 1 <= depth < n: # 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 한다. 라고 했으므로 다음과 같이 범위를 설정 해준다.
        first, second = 0, 0 # 이전 값이 남아있지 않도록 초기화 해줘야 한다.
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j]:
                    first += pan[i][j]
                elif not visited[i] and not visited[j]:
                    second += pan[i][j]
        answer = min(answer, abs(first-second))

    for i in range(idx, n): # 조합을 이용한 백트래킹을 통해 팀을 나눈다.
        if not visited[i]:
            visited[i] = True
            dfs(depth+1, i+1)
            visited[i] = False

dfs(0, 0)
print(answer)

    

설명

백트래킹(완전탐색)을 활용한 문제

참고 자료