[백준 14889번] 스타트와 링크

14889번: 스타트와 링크

n = int(input())

visited = [False for _ in range(n)]

data = [list(map(int, input().split())) for _ in range(n)]

min_value = float("inf")

def dfs(depth,index):
    global min_value

    if depth == n//2:
        power1, power2 = 0, 0
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j]:
                    power1 += data[i][j]
                elif not visited[i] and not visited[j]:
                    power2 += data[i][j]
        min_value = min(min_value,abs(power1-power2))
        return
    for i in range(index,n):
        if not visited[i]:
            visited[i] = True
            dfs(depth+1,i+1)
            visited[i] = False

dfs(0,0)

print(min_value)

이번 문제는 N명의 팀원을 2개의 팀으로 나눠 팀 능력치를 각각 구한 뒤 두 팀의 능력치 차이의 최솟값을 구하는 문제이다.

 

결국 팀을 2개로 나누는 모든 경우의 수를 구해야 하는데, 두 팀을 리스트나 집합으로 저장해서 dfs의 인자로 전달하니 시간초과가 발생하였다.

 

다른 사람의 풀이를 참고해본 결과, visited 리스트로 한 팀만 찾으면 나머지 팀원들이 정해지기 때문에 시간복잡도를 최소화하여 풀이할 수 있다.