문제

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

나의 코드

"""

"""

from itertools import combinations
from sys import stdin
input = stdin.readline

n = int(input())
pan = [ list(map(int, input().split())) for _ in range(n) ]
team = [ i for i in range(1, n+1) ]
team = list(combinations(team, n//2)) # 조합을 이용해 팀을 나눔
lp, rp = 0, len(team)-1
answer = 1e9

def team_sum(stat): # 팀의 능력치의 합을 구하는 함수

    sum = 0
    stat = list(combinations(stat, 2)) # 만약 3개 이상으로 나뉜다면 조합을 통해 능력치 합을 구하기 위해 또 나눠야 한다.

    for i, j in stat:
        sum += pan[i-1][j-1] + pan[j-1][i-1]

    return sum

while lp <= rp: # 가장 왼쪽과, 오른쪽에서 중간으로 오면서 반복문을 돌림

    first_team = team_sum(team[lp])
    second_team = team_sum(team[rp])
    answer = min(answer, abs(first_team-second_team)) # 능력치의 합의 차를 이용해 최솟값을 구함

    lp, rp = lp+1, rp-1

print(answer)

    

다른 풀이 코드

"""

"""

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 depth == n//2: # 팀이 나눠진다면 능력치의 합을 구해 차를 통해 최솟값을 구한다.
        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)

    

설명

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

참고 자료