백준 14889 - 스타트와 링크 (파이썬)

분류 : 브루트포싱

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

풀이

문제 분석을 하면 다음과 같다.

1. N명의 사람을 두 개의 팀으로 나누어야한다.
2. S[i][j]는 i번 사람과 j번 사람이 같은 팀일때 더해지는 능력치이다.
3. 두팀의 능력치 차이를 최소화 해야한다.
4. 능력치는 대팅이 아닐 수 있으며, 대각선 값은 항상 0이다.

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

예제의 값을 생각해보면 다음과 같이 풀이 할 수 있다. 일단 가능한 팀 조합은 다음과 같다.

1. (1, 2) vs (3 , 4) → 능력치 차이 | 5 - 7 | = 2
2. (1, 3) vs (2, 4) → 능력치 차이 | 9 - 10 | = 1
3. (1, 4) vs (2, 3) → 능력치 차이 | 6 - 6 | = 0

문제 풀이를 위한 해결 방법은 다음과 같다.

1. 조합을 이용한 팀 나누기
   1. N명의 사람 중 N / 2 명을 선택하는 모든 경우의 수를 생성해야한다.
   2. 조합을 사용하면 쉽게 구할 수 있다.
2. 능력치 계산
   1. 선택된 팀에 대해 모든 (x, y) 쌍에 때해 능력치를 더한다.
   2. 나머지 인원을 다른 팀으로 구성하고 동일하게 계산한다.
3. 차이값 갱신
   1. 두팀의 능력치 차이의 최솟값을 갱신하면서 탐색한다.
   2. 차이가 0 이면 조기 종료한다.

시간복잡도를 분석해보면, combinations(range(N), N // 2) 의 갯수는 N choose N / 2

최대 N = 20d일때, (20 choose 10) = 184,756으로 충분히 계산 가능하다.

이중 for문으로 능력치를 합산하므로 O(N^2 * 2 ^ N) 정도의 연산이지만 20 이하에서 충분히 해결 가능하다.

코드

# 백준 14889 - 스타트와 링크
# 분류 : 브루트포싱

from itertools import combinations

N = int(input())
S = [[] for _ in range(N)]

for i in range(N):
    S[i] = list(map(int, input().split()))

min_diff = 1e9

for combination in combinations(list(range(N)), N // 2) :
    team_a = combination
    team_b = []
    for i in range(N) :
        if i not in team_a :
            team_b.append(i)
    
    power_a = 0
    power_b = 0

    for x in team_a :
        for y in team_a :
            power_a += S[x][y]
    
    for x in team_b :
        for y in team_b :
            power_b += S[x][y]
    
    diff = abs(power_a - power_b)
    if min_diff > diff :
        min_diff = diff

print(min_diff)