[백준알고리즘] 14889번: 스타트와 링크 -Python

[백준알고리즘] 14889번: 스타트와 링크 -Python

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

브루트 포스방식으로 문제를 풀었다.

 

N//2명의 인원씩 A, B팀으로 나누어주었다. 이때 모든 팀원 배치를 하기 위해서 itertools의 combinations를 사용했다.

 

구한 팀 배치마다 각 팀원들의 모든 팀 능력치를 합해주기 위해서 이중 for문을 돌렸다.

from sys import maxsize
from itertools import combinations

n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
cb = combinations(range(n), n//2)
ans = maxsize

for c in cb:
    a = set(c)
    b = list(set(range(n)) - a)
    a = list(a)

    a_teamwork, b_teamwork = 0, 0

    for i in range(n//2 - 1):
        for j in range(i + 1, n//2):
            a_teamwork += s[a[i]][a[j]] + s[a[j]][a[i]]
            b_teamwork += s[b[i]][b[j]] + s[b[j]][b[i]]

    ans = min(ans, abs(b_teamwork - a_teamwork))

print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다