백준 22.01.31. 14889번 - 스타트와 링크

from itertools import combinations

N = int(input())

matrix = [list(map(int, input().split())) for i in range(N)]
teamComb = list(combinations(range(N), N//2))
result = []
for i in range(len(teamComb)//2):
    teamS = teamComb[i]
    statS = 0
    for j in range(N//2):
        colS = teamS[j]
        for rowS in teamS:
            statS += matrix[colS][rowS]

    teamL = teamComb[-i-1]
    statL = 0
    for j in range(N//2):
        colL = teamL[j]
        for rowL in teamL:
            statL += matrix[colL][rowL]

    dif = abs(statS - statL)
    if dif not in result:
        result.append(dif)

print(min(result))

• 팀이 이룰 수 있는 멤버의 조합을 구했을 때, 다른팀은 그 반대되는 조합을 가지는 것을 알 수 있습니다.
• 따라서 combinations를 이용하여 인원의 절반인 수가 한 팀이 될 수 있는 조합을 모두 구해줍니다.
• 이어서 Link팀과 Start팀을 나누어 Start팀이 첫 인덱스부터 탐색을 시작한다면 Link팀은 그 반대로 끝에서부터 역순으로 탐색을 시작합니다.

  • 

    combinations로 얻은 결괏값을 보면 서로 대칭되는 인덱스의 요소는 중복되지 않습니다.
• 팀 조합을 골라 teamS, teamL로 지정해줍니다
• 조합안에서의 두 선수 조합의 스탯값을 구하기 위해서 teamS에서의 값으로 matrix에서의 row, col값을 인덱스로 할당해줍니다.
• S¡¡ 와 같은 같은 선수가 중복되는 조합의 스탯은 0이므로 굳이 제외하지 않았습니다.
• 고른 팀 조합에서의 모든 선수 조합의 스탯을 더해주고 구한 teamL과 teamS의 스탯을 뺀 절대값을 result에 저장합니다.
• 모두 다 구했다면 result의 최솟값을 출력합니다.