[백준] 14889번 스타트와 링크 (by Python)

문제

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

14889번: 스타트와 링크

 

첫 번째 풀이

처음 생각하게 된 풀이는 브루트 포스 방식입니다. itertools의 combination을 이용해 가능한 조합들을 모두 구하고 그에 따른 각 팀의 능력차를 구하는 방법인데, 여기서 (1, 2, 3, 4) / (5, 6, 7, 8)로 팀이 나뉘었을 때와 (5, 6, 7, 8) / (1, 2, 3, 4)로 팀이 나뉘었을 때를 별도의 경우로 보면 시간복잡도가 더 커지므로 이를 해소하기 위해 우리 팀에는 항상 1이 있다고 가정하고 뽑았습니다.

 

from itertools import combinations

n = int(input())
arr = [[0] * (n + 1)]
ans = int(1e9)
whole = set(range(1, n + 1))

for i in range(n):
    arr.append([0] + list(map(int, input().split())))

for com in combinations(range(2, n + 1), n // 2 - 1):
    our = set([1]) | set(com)
    enemy = whole - our
    diff = abs(sum(arr[x][y] for x in our for y in our - set([x])) - sum(arr[x][y] for x in enemy for y in enemy - set([x])))
    ans = min(ans, diff)
    if ans == 0: break

print(ans)

 

두 번째 풀이

첫 번째 풀이로도 문제가 해결되긴 했으나, 소요 시간이 너무 길었던 탓에 훨씬 시간이 덜 소요되는 다른 분들의 풀이의 아이디어를 참고하여 두 번째 풀이 또한 시도해보게 되었습니다. 여기에서 핵심 아이디어는 두 팀의 능력치 차이를 구할 때에 있어서의 방법입니다. 모든 팀원 i에 대해서 주어진 행렬에서 i번째 행과 열의 값을 모두 더함으로써 해당 팀원이 포함된 모든 경우의 능력치 합 s_i를 구합니다. 그리고 행렬 값의 총합에서 선택된 팀원들 k의 능력치 합인 sum(s_k)를 빼면 상대 팀과의 차이가 됩니다. 이게 어떻게 가능한지는 머릿속에 행렬을 그려보시고 특정 행과 열들을 빼는 상상을 해보시면 이해가 가실 겁니다. 코드는 다음과 같습니다.

 

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

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
each = [sum(x) + sum(y) for x, y in zip(arr, zip(*arr))]
total = sum(each) // 2

print(min(abs(total - sum(each[e] for e in c)) for c in combinations(range(1, n), n // 2)))