[python] 백준 15661 링크와 스타트

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

15661번: 링크와 스타트

 

문제 해결

팀을 정하는 것부터 하나 하나 다 해봐야 하기 때문에 상당히 시간복잡도가 클 것 같다.(팀원 수도 양수라는 것 외에 정해지지 않음)

결국 팀원 하나하나 정하는 것을 재귀를 통해서 정리하고 계산을 하여 최솟값을 구한다.

파이썬으로는 시간초과가 나와서 pyp3로 풀었다.

 

CODE

import sys
input = sys.stdin.readline
INF = sys.maxsize
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
ans = INF
visited = [0 for _ in range(n)] # 0팀과 1팀으로 나눔

def cal_it():
    global ans
    start, link = 0, 0
    for i in range(n):
        for j in range(n):
            if visited[i] and visited[j]: # i와 j가 1팀일 때
                start += graph[i][j]
            elif not visited[i] and not visited[j]: # i와 j가 0팀일 때
                link += graph[i][j]
    ans = min(ans ,abs(start-link))
    return

def solve(iter):
    if iter == n: # n개의 원소들이 다 팀이 정해졌을 때 시너지 계산
        cal_it()
        return
    visited[iter] = 1
    solve(iter+1)
    visited[iter] = 0
    solve(iter+1)

solve(0)
print(ans)