백준 | 스타트와 링크

백준 스타트와 링크

combinations 함수를 통해 0부터 (n - 1)까지의 값을 두 그룹으로 나눌 수 있는 모든 경우를 구했다.
이후 각 경우에서 두 그룹의 능력치 합을 계산한 뒤, 구하고자 하는 두 팀의 능력치 차이 최솟값을 업데이트하면 된다.

# 정답

import sys
from itertools import combinations

# 입력
n = int(sys.stdin.readline())
s = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# min_score_diff: 두 팀의 능력치 차이 최솟값
min_score_diff = float('inf')

for start in combinations(range(n), n // 2):
    # start: 스타트 팀에 속하는 사람들의 번호
    start = set(start)
    # link: 링크 팀에 속하는 사람들의 번호
    link = set(range(n)) - start

    start_score_sum = 0
    for i, j in combinations(start, 2):
        start_score_sum += (s[i][j] + s[j][i])
    
    link_score_sum = 0
    for i, j in combinations(link, 2):
        link_score_sum += (s[i][j] + s[j][i])

    score_diff = abs(start_score_sum - link_score_sum)
    min_score_diff = min(min_score_diff, score_diff)

    if min_score_diff == 0:
        break

# 출력
print(min_score_diff)

위의 풀이는 약 4196ms가 소요되는데..
백트래킹을 이용하면 2340ms 정도로 시간을 줄일 수 있다.

# 정답

import sys

def dfs(num, start, link):
    global min_score_diff

    # 두 팀의 능력치 차이가 0이라면 더 이상 탐색할 필요가 없다.
    if min_score_diff == 0:
        return 0

    # 두 팀이 m명과 m명으로 나눠진 경우, 능력치 차이를 계산한다.
    if num == n:
        if len(start) == m and len(link) == m:
            start_score_sum = 0
            link_score_sum = 0

            for i in range(m):
                for j in range(m):
                    start_score_sum += s[start[i]][start[j]]
                    link_score_sum += s[link[i]][link[j]]
            
            score_diff = abs(start_score_sum - link_score_sum)
            min_score_diff = min(min_score_diff, score_diff)
        
        return 0

    # 번호가 num인 사람이 스타트 팀으로 가는 경우
    dfs(num + 1, start + [num], link)
    # 번호가 num인 사람이 링크 팀으로 가는 경우
    dfs(num + 1, start, link + [num])

# 입력
n = int(sys.stdin.readline())
s = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

min_score_diff = float('inf')
m = n // 2

dfs(0, [], [])
print(min_score_diff)