이제 itertools를 자유자재로 쓰는 나 ... 멋져 ...

1. 내 풀이: 성공

import sys
from itertools import combinations, permutations
input = sys.stdin.readline

n = int(input()) # 짝수
s = []
for _ in range(n):
    s.append(list(map(int, input().split())))

minTotal = 100*(n**2)
for comb in combinations(range(n), n//2):
    total = 0
    sum_start = 0
    sum_link = 0
    start = list(comb)
    link = [i for i in range(n) if i not in start]
    for pair in permutations(start, 2):
        sum_start += s[pair[0]][pair[1]]
    for pair in permutations(link, 2):
        sum_link += s[pair[0]][pair[1]]
    minTotal = min(minTotal, abs(sum_start-sum_link))

print(minTotal)

쫄리게 1퍼센트씩 올라갔다가 청량하고도 아름다운 맞았습니다 ~!!~~ 를 봤다.
풀이는 다음과 같다.

입력값들을 받는 건 쉬우니 패스하고, 방법만 설명해보겠다.

일단 인원수만큼 받은대로 팀을 절반씩 나눌 수 있도록 combination을 해준다. 그러면 총 인원 중 골라진 값들이 있을텐데, 이를 통해 start 팀과 link 팀으로 나누어준다. 그리고 그에 맞게 각각의 합을 구해주고, 이를 빼서 그 팀 간의 능력치 차이를 구한다.

2. 다른 풀이: 백트래킹

def dfs(depth, idx):
    global min_diff
    if depth == n//2:
        power1, power2 = 0, 0
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j]:
                    power1 += graph[i][j]
                elif not visited[i] and not visited[j]:
                    power2 += graph[i][j]
        min_diff = min(min_diff, abs(power1-power2))
        return

    for i in range(idx, n):
        if not visited[i]:
            visited[i] = True
            dfs(depth+1, i+1)
            visited[i] = False


n = int(input())

visited = [False for _ in range(n)]
graph = [list(map(int, input().split())) for _ in range(n)]
min_diff = int(1e9)

dfs(0, 0)
print(min_diff)

풀이 출처: https://developer-ellen.tistory.com/50

백트래킹으로 푸는 방법이다. 백트래킹으로 풀 때의 템플릿은

• if문 : DFS를 멈출 수 있는 조건 ➡️ 여기서 만들어진 경우의 수에 따라 필요한 계산을 함
• for문 : DFS 가지치기
• visited 배열 : 일단 False 로 초기화 해두고, 경우의 수를 만들 때 얘를 체크했나 안했나 확인하는 용도
• visited[i] = True : DFS 들어갈 때는 True, 나올 때는 False (다른 곳에서는 append - pop)

이런 것 같다.

3. 마치며

브루트포스 실버 ...! 이제 조금씩 풀만해지는 것 같다 !!! 감 놓치지 않기 위해 좀만 더 풀고 다음 알고리즘으로 넘어가자 ㅎㅎ ~ !!!