[백준] 14889. 스타트와 링크 / python 파이썬

🚩 브루트포스, 백트래킹

 

thinking

1. 파이썬 itertools의 조합 기능을 사용해 만들수 있는 리스트의 경우의 수를 구하고

2. for문을 돌면서 해당 경우의 수의 행만 돌면서 나머지 열의 값을 더함
    ex. (1,2,3)의 경우라면 1,2,3행을 돌며 1행일 때는 2,3열의 값,
    2행일 때는 1,3열의 값, 3행일 때는 1,2열의 값만 더하면 팀의 능력치를 구할 수 있다.

3. sumA, sumB 구한 다음 abs로 차이 구해서 가장 최소값이 답

 

❗ 문제는 (1,2,3)-(4,5,6) / (1,4,5)-(2,3,6) 이런식으로 짝을 이루어야하는데 이걸 어떻게 매칭시키는 것인가였다.

근데 대박인게 itertools로 조합 구하면 아래 그림처럼 알아서 순서대로 조합의 경우를 구해서 매칭이 된다.

그래서 절반으로 나눈다음 앞 섹션은 앞에서부터, 뒷섹션은 뒤에서부터 인덱스를 할당해주었다

 

코드

from itertools import combinations

# Sij 합 구하는 함수
def subsum(tp1, tp2):
    sumA, sumB = 0, 0
    for i in tp1:
        for j in tp1:
            sumA += S[i][j]
    for i in tp2:
        for j in tp2:
            sumB += S[i][j]
    return abs(sumA-sumB)


N = int(input())
S = [list(map(int, input().split())) for _ in range(N)]  # Sij: 1~100

comb_lst = list(combinations(range(N), N//2))
res = 987654321
for i in range(len(comb_lst)//2):
    tmp = subsum(comb_lst[i], comb_lst[len(comb_lst)-1-i])
    if tmp < res:
        res = tmp

print(res)