스타트와 링크

문제

N명의 사람들에게 1부터 N까지 번호를 배정하고 능력치를 조사합니다.
능력치 S_ij는 i번 사람과 j번 사람이 같은 팀에 속했을때 팀에 더해지는 능력치입니다.
팀을 절반으로 나눴을때 두팀의 능력치 차이가 최소가 되는 경우를 구하는 문제입니다.

제약조건

• S_ij와 S_ji는 다를 수 있습니다.
• 4 <= N <= 20 (N은 짝수입니다.)
• 1 <= S_ij <= 100 (S_ij는 정수입니다.)

풀이

1 ~ N로 번호지어진 사람들을 N/2개 뽑는 경우의 수를 모두구합니다.
N = 20일때 20! / (10! * 10!) = 184756 가지를 뽑습니다.
이때 나열된 사람들을 유심히 살펴보면 , 순서대로 뽑아 조합을 이루기때문에 "정렬"된 상태임을 알수있습니다.이점을 이용해서 앞의 N/2 경우의수와 뒤집어진 뒤의 N/2개의 경우의수을 그룹화하면 스타트와 링크로 나뉘어진 하나의 경우의 수를 만들 수 있습니다.

N = 4일때의 예시를 들면 (파랑색은 원래의 공을 뒤집었을때를 표현한것입니다.)

이제 N명을 두 그룹으로 나누는 모든 경우의 수를 얻었습니다.
각 경우의 수에서 2개를 뽑는 순열을 계산하여 각각의 능력치 계산을 한뒤 능력치 차이를 계산해서 최소를 가지는 결과를 반환합니다.

코드

'''
Created by jun on 21/05/19
'''
from itertools import combinations, permutations
import sys

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
#모든 가능한 팀의 조합을 계산합니다.
all_team = list(combinations(range(N), N//2))
#두 팀으로 나눕니다.
start_team = all_team[:len(all_team)//2:]
link_team = all_team[-1:len(all_team)//2-1:-1]

res = sys.maxsize

#두개로 나눈 팀에 대하여 능력치 차이를 계산합니다.
for start_team, link_team in zip(start_team, link_team):
    start_team_ability = 0
    #능력치가 앞뒤로 다르므로 2개의 경우 모두 고려합니다.
    for ability in permutations(start_team, 2):
        start_team_ability += board[ability[0]][ability[1]]

    link_team_ability = 0
    for ability in permutations(link_team, 2):
        link_team_ability += board[ability[0]][ability[1]]

    res = min(res, abs(start_team_ability-link_team_ability))

print(res)

새로 알게된 사실

모든 조합을 두개로 나누는 방법.