[BOJ 14889] 스타트와 링크(Python)

---

문제

스타트와 링크

---

문제 해설

조합을 이용해 각 팀의 시너지를 계산하는 문제입니다.

먼저 사람이 최대 20명이고, 팀을 나누는 방법의 수는 20C10 이므로 184756의 가짓 수가 나오게 됩니다. 하지만 팀을 두개로 나누기 때문에 중복되는 계산이 발생합니다. 그래서 조합의 개수를 반으로 줄이게 되면 쓸데없는 계산을 피할 수 있습니다.

1. N명 중 N/2명을 뽑는 조합을 구합니다.
2. team1에는 1의 조합을, team2에는 1에 포함되지 않은 사람들을 넣습니다.
3. 각 팀당 2명씩 뽑아 시너지를 계산합니다.

---

풀이 코드

from itertools import combinations
import sys

input = sys.stdin.readline
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
answer = sys.maxsize

half = 1  # 조합의 수 // 2
for i in range(n, n // 2, -1):
    half *= i
for i in range(1, n // 2 + 1):
    half //= i
half //= 2

cnt = 0
for com in combinations([i for i in range(n)], n // 2):
    team1, team2 = 0, 0
    if cnt == half:  # 전체 조합 개수의 반까지만 실행하면 끝
        break
    others = []
    for i in range(n):
        if i not in com:  # 조합으로 뽑히지 않은 번호 다른팀에 배정
            others.append(i)
    # 각 팀당 2명씩 뽑아 시너지 계산
    for a, b in combinations(com, 2):
        team1 += graph[a][b] + graph[b][a]
    for a, b in combinations(others, 2):
        team2 += graph[a][b] + graph[b][a]
    answer = min(answer, abs(team1 - team2))
print(answer)

---