BOJ : 14889 스타트와 링크

computeAbility(team) : team 배열에 속한 사람들과 team 배열에 속하지 않은 (다른 팀) 사람들을 이용하여 두 팀의 능력 차이를 계산하여 return

makeTeam() : 가능한 조합의 팀을 만들어낸다.
예를 들어 4명의 사람이 있으면 [0,1], [0,2],[0,3],[1,2],[1,3] 을 만든다.
팀이 만들어지면 ( 배열의 length == 전체 인원수 /2) computeAbility() 함수를 이용하여 능력치 차이를 구하고 min_abil과 비교한다.

mean_abil : 가장 작은 능력치 차이를 저장한다.

import sys

# 팀 능력치 차이의 최소를 출력한다

# team ability 를 계산하고 team 에 포함되지 않은 사람들을 계산하여 차이를 return
def computeAbility(team):
    sum1= 0
    for a in team:
        for b in team:
            sum1+=ability[a][b]
    sum2 = 0
    # print(team)
    team2 = list(filter(lambda x : x not in team, people_list))
    # print(team2)
    for a in team2:
        for b in team2:
            sum2+=ability[a][b]
    return sum1 - sum2

def makeTeam(arr):
    global min_abil
    # print(arr)
    if len(arr) < people_num/2:
        if len(arr) == 0:
            for people in people_list[:people_num//2]:
                makeTeam(arr + [people])
        else:
            for people in people_list:
                if arr[-1] < people:
                    makeTeam(arr + [people])

    else:
        ability = abs(computeAbility(arr))
        if min_abil == -1:
            min_abil = ability
        elif min_abil > ability:
            min_abil = ability

people_num = int(sys.stdin.readline())

# ability[i][j] 는 i번사람과 j번 사람이 같은 팀에 속할 때 팀에 속해지는 능력치
ability = [ list(map(int, sys.stdin.readline().strip().split())) for _ in range(people_num)]

# 능력치 차이 최소값
min_abil = -1
people_list = [i for i in range(people_num)]
# n/2 길이의 배열을 만든다
makeTeam([])
print(min_abil)