백준 14889 - 스타트와 링크

 

처음 든 생각

- 조합을 백트래킹으로 구현해서 팀을 만든 다음, 나머지 팀도 구해서 각각의 능력치를 비교해주면 되겠다.

 

나의 답

import sys
input = sys.stdin.readline

N = int(input())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))

result= 10000
t1 = []
def f(p):
    if len(t1) == N//2:
        global result    
        t2 = [j for j in range(N) if j not in t1]
        sum1 = 0
        for k in t1:
            for l in t1:
                sum1 += arr[k][l]
        for m in t2:
            for n in t2:
                sum1 -= arr[m][n]
        result = min(result, abs(sum1))
        return
    else:
        t1.append(p)
        for i in range(p,N):  
            f(i+1)
        t1.pop()
f(0)    
print(result)

 

 

팀 하나를 결정 지으면 나머지는 알아서 결정되므로, N//2명의 팀을 구하는 게 우선이다.

 

인덱스를 기준으로 팀을 구성하게 된다.

아직 팀이 결정되지 않으면, 해당 인덱스를 추가하고 반복문으로 그 뒤의 인덱스에 대해 탐색을 한다.

 

N=6일 때를 예시로 한 번 살펴보자.

 

(순서대로)

f(0), t1 = [0]

f(1), t1 = [0,1] ---- (a)

f(2), t1 = [0,1,2]

f(3),f(4), f(5), f(6) 3개 채워졌으므로 결과 계산

f(2)에 대한 pop 수행 t1 = [0,1]

(a)에 있던 반복문에서 f(2) 끝났으니깐 f(3) 수행, t1=[0,1,3]

f(4),f(5),f(6) 3개 채워졌으므로 결과 계산

....

 

이런 식으로 수행해나가는 매커니즘의 백트래킹이였다.

 

처음에 이 문제를 풀 때 메모리 초과가 났었는데, 3개짜리 조합을 다 구해놓고 구하는 방식으로 알고리즘을 구현했었다. 조합의 경우 공간복잡도가 N! / (N//2)!(N//2)! 이므로 어쨌든 팩토리얼 단위로 나오게 된다. 20!의 경우 19자리 수이므로 공간복잡도가 클 수 밖에 없었다.

 

해당하는 조합을 찾을 때마다 바로바로 연산처리를 하는 과정으로 수정해서 문제를 해결할 수 있었다.