문제 파악 및 접근 방법

• 문제 링크 : https://www.acmicpc.net/problem/14889

• 팀을 두 개로 나누고 두 팀의 능력치의 차이를 최소로 하려고 한다.

• 4 ≤ N ≤ 20 이므로 이진 트리 형태의 백트래킹 조합으로 2^20 = 10^6 이므로 시간 내에 풀이할 수 있다.
  

코드 설계

• dfs를 통해 모든 가능한 경우의 수를 확인한다.
  • 종료 조건 : n == N (N : 학생 수)
    • a팀, b팀 수가 같을 경우 정답 갱신
  • 하부 호출
    • a팀을 선택하는 경우
    • b팀을 선택하는 경우

코드 구현

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
M = N // 2

# 두 팀의 능력치 차이를 계산하는 함수
def cal(alst, blst):
    aSum, bSum = 0, 0
    for i in range(M):
        for j in range(M):
            aSum += arr[alst[i]][alst[j]]
            bSum += arr[blst[i]][blst[j]]
    return abs(aSum - bSum)

def dfs(n, alst, blst):
    global answer

    if n == N:  # 종료 조건
        # 같은 인원으로 팀을 구성했을 경우
        if len(alst) == len(blst):
            answer = min(answer, cal(alst, blst))
        return

    # a 팀을 선택하는 경우
    dfs(n+1, alst+[n], blst)

    # b 팀을 선택하는 경우
    dfs(n+1, alst, blst+[n])

answer = float("inf")
dfs(0, [], [])
print(answer)

제출 결과