#321 백준 파이썬 [14889] 스타트와 링크

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

 

SOLUTION

조합으로 모든 팀 조합을 구해준 뒤, 각각의 팀 능력치를 생성해 비교하면 된다.

0~n까지 조합을 생성하여 리스트에 담으면 첫 조합의 여집합은 마지막 조합이다.

즉 team[i] 는 team[-i-1]과 완전히 반대된다. 이를 이용하여 풀면 쉽다.

PYTHON CODE

from itertools import combinations #조합 함수

N = int(input())
S = [list(map(int, input().split())) for _ in range(N)]
members = [i for i in range(N)]
possible_team = []

#조합으로 가능한 팀 생성해주기
for team in list(combinations(members, N//2)):
    possible_team.append(team)

min_stat_gap = 10000 #갭이 가장 작은 값을 찾기 위하여
for i in range(len(possible_team)//2):
    #A 팀
    team = possible_team[i]
    stat_A = 0 #A팀 능력치
    for j in range(N//2):
        member = team[j] #멤버
        for k in team:
            stat_A += S[member][k] #멤버와 함께할 경우의 능력치들
            
    #A를 제외한 나머지 팀
    team = possible_team[-i-1]
    stat_B = 0
    for j in range(N//2):
        member = team[j]
        for k in team:
            stat_B += S[member][k]
            
    min_stat_gap = min(min_stat_gap, abs(stat_A - stat_B))
    
print(min_stat_gap)