[백준14889] 스타트링크

문제

---

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

14889번: 스타트와 링크

 

생각의 흐름

---

combinations() 메소드를 이용하여 team1의 조합을 구한 뒤 그에 대응되는 team2의 조합을 구해 각 team의 구성원들의 능력치합 sum1, sum2를 구해 차이를 비교해주면 된다. 단순히 "차이"이므로 abs()를 써주어야 한다.

 

코드

---

# BOJ 14889

import itertools
import sys

n = int(input())
mat = [list(map(int, input().split())) for _ in range(n)]
member = [i for i in range(n)]
gap = sys.maxsize
tt = list(itertools.combinations(member, n//2))
for team1 in tt:
    sum1, sum2 = 0, 0
    team2 = [x for x in member if x not in team1]
    for x, y in (itertools.combinations(team1, 2)):
        sum1 += mat[x][y] + mat[y][x]
    for x, y in (itertools.combinations(team2, 2)):
        sum2 += mat[x][y] + mat[y][x]
    gap = min(gap, abs(sum1-sum2))
print(gap)