백준 14889) 스타트와 링크 (실버.2)

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

14889번: 스타트와 링크

 

 

문제의 조건은 다음과 같다. 

1) 총 사람수는 짝수로 이루어져 있다.

2) 팀원수는 각각 n/2명이 된다 

3) 팀원 각각의 쌍의 능력치를 더한 값이 팀이 능력치가 된다 

4) 팀별로 능력치가 가장 작을 때의 차이 출력

 

가장 먼저 생각한 것은 팀원의 조합을 이용하여 모든 팀이 생성되는 경우의 수를 구하고 각각의 팀점수를 구해서 차이의 최솟값을 찾는 해법을 생각했다. 

from itertools import combinations
from math import inf

n = int(input())
people = [i for i in range(n)]
global power
power = [[] for _ in range(n)]
for i in range(n):
    power[i].extend(list(map(int, input().split())))

teams = list(combinations(people, n//2))

min_sub = inf

def getScore(pairs) :
    global power
    score = 0 
    for pair in pairs : 
        if pair[0] == pair[1] :
            continue
        score += (power[pair[0]][pair[1]] + power[pair[1]][pair[0]])
    return score

for i in range(len(teams)//2):
    t_start = teams[i]
    t_link = teams[len(teams)-1-i]

    s_pairs = list(combinations(t_start, 2))
    l_pairs = list(combinations(t_link, 2))

    min_sub = min(min_sub, abs(getScore(s_pairs)- getScore(l_pairs)))


print(min_sub)

 

 

조합의 경우 다음의 식을 갖게 되는데 여기서 계산의 시간복잡도는 O(nCr)을 나타내게 된다. 

참고로 순열의 경우 다음과 같다(순서고려)

시간 복잡도: O(n!) (n개를 뽑는 모든 경우의 수 구할 때)
공간 복잡도: O(n*n!) 

r개를 뽑을 때 : O(nCr * r)!

 

 

itertools의 경우에 시간복잡도가 O(n^2)이 되기 때문에 경우의 수가 작은 게 아니라면 사용하지 않는 것이 좋다는 것을 보게되었다. 

또, 여기서는 t_start, t_link, s_pairs, l_pairs를 경우의 수마다 계속해서 만들어내기 때문에 공간복잡도도 높을 것으로 예상이 되었다. 

 

 

그래서 다음의 dfs를 이용해서 탐색하여 depth가 n//2가 되었을 때 각각의 점수의 최소 차를 구하는 식을 구현하였다. 

from math import inf
global n, power, visited, min_sub
n = int(input())
power = [[] for _ in range(n)]
for i in range(n):
    power[i].extend(list(map(int, input().split())))
visited = [False]*(n)
min_sub = inf

def dfs(depth, idx):
    global n, power, visited, min_sub
    if depth == n//2 : 
        t_start, t_link = 0, 0 
        for i in range(n):
            for j in range(i+1, n):
                if visited[i] and visited[j]:
                    t_start += (power[i][j] + power[j][i])
                elif not visited[i] and not visited[j]:
                    t_link += (power[i][j] + power[j][i])
        min_sub = min(min_sub, abs(t_start - t_link))

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

dfs(0, 0)
print(min_sub)