[baekjoon] 14889. 스타트와 링크

---

로직

1. 조합으로 start팀 가능한 경우의 수를 모두 구한다음에 모든 경우에서 link팀도 구한다. 그래서 차이 비교하기

 

코드

from itertools import combinations

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]

# combination 함수로 만들기
people = [i for i in range(N)]
start = list(combinations(people, N//2))  # // : 나눗셈 후 몫 반환, / : 7/4=1.25
all_people = set(people)

mymin = 9999999999999999999999999999999999
for star in start:
    link = list(all_people - set(star))

    link_sum = 0
    start_sum = 0
    for i in range(N//2 - 1):
        for j in range(i+1, N//2):
            start_sum += board[star[i]][star[j]] + board[star[j]][star[i]]
            link_sum += board[link[i]][link[j]] + board[link[j]][link[i]]

            diff = abs(start_sum - link_sum)

    if mymin > diff:
        mymin = diff

print(mymin)