백준_14889_스타트와 링크(백트래킹)

from itertools import combinations
import math
n = int(input())
team = [[0]*n for _ in range(n)]
com = list(combinations(range(n), n//2))

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

stance = math.inf

for i in range(len(com)//2):
    start = link = 0
    for x, y in combinations(com[i], 2):
        start += (team[x][y] + team[y][x])
    for x,y in combinations(com[len(com)-i-1], 2):
        link += (team[x][y] + team[y][x])
    stance = min(abs(start - link), stance)
print(stance)

백트래킹 문제이지만 주어진 combination으로 풀 수 있어 그냥 combination으로 해결했다.

경우의 수를 combination을 사용해서 구한 후 각 경우에 대해 for문을 돌면서 각 팀의 능력치 값 차이의 최소 값을 구하는 방식이다.

이전에 풀 때는 백트레킹 방식으로 어떻게 풀었는지 확인하려고 했지만 이전에 풀 때에도 같은 방식으로 했었었다...