[백준] 14889 스타트와 링크(python)

14889 스타트와 링크

문제

축구를 하기 위해 모인 N명을 두팀으로 나눠야 한다. 두 팀의 능력치 차이의 최솟값을 구해야한다.
능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력은 Sij와 Sji이다.

구현

축구에 참여하는 인원과 능력치를 입력받는다.
[코드 설명]
1. 2개의 팀으로 분배를 combination함수를 이용해 조합을 구한다.

combination함수
n개의 원소를 사용해서 r개의 배열로 나타내는 경우
itertools.combinations(n, r)

2. 두 팀의 능력치 차이를 계산한다.
   1에서 구한 조합에 포함된 사람들의 능력치와 조합에 포함되지 않은 사람들의 능력치를 구한 후 두 팀의 능력치 차이를 구한다.

[코드]

import itertools

n=int(input())

people=[i for i in range(n)]
S=[[0] for _ in range(n)]

for i in range(n) :
    S[i]=list(map(int, input().split()))

#순열을 이용하여 짝수로 2개의 팀을 나눔
teams=list(itertools.combinations(people, int(n/2)))
min=100*n*n
for team in teams : #두 팀의 능력치 차이 계산
    team_A=0
    team_B=0
    for i in team : #순열로 짝 지은 팀에 포함된 사람들의 능력치 구함
        for j in team:
            team_A+=S[i][j]
    not_team=[x for x in range(n) if x not in team] #순열로 구한 팀에 속하지 않는 사람들
    for i in not_team :
        for j in not_team :
            team_B+=S[i][j]
    
    if min>abs(team_A-team_B) :
        min=abs(team_A-team_B)

print(min)