악곱 == 악성곱슬

브루트 포스

---

이 문제는 팀을 2개로 나눠서 각 팀원의 전력의 차이가 최소가 되도록 구현하는 문제인데, 팀원 수에 제한이 없다. 그래서 어떻게 풀어야 할까 고민을 하다가, 방법이 없고 완전탐색을 해야 함을 깨달았다.

완전 탐색을 해도, $21 C 10$ 으로 35만개의 조합이 나오는데, 이를 각각 계산해서 구해도 시간초과가 아슬아슬하게 나오지 않을 것이라고 생각했다. $21C10$ 인 이유는, 20C2 + ... + 20C10 을 구해도 더 큰 값으로 시간복잡도의 워스트 케이스를 고려한 것이다.

구현

---

아래 코드는 python3에서는 시간초과를 받았다 ㅜ.ㅜ 중복 문제가 포함되어 있어서 그런 것 같다. 어떻게 해결해야 할지 고민해봐야겠다.

pypy3로는 통과했다.

import sys

def calculate(array):
    result = 0
    for i in range(len(array)):
        for j in range(i+1, len(array)):
            result += graph[array[i]][array[j]] + graph[array[j]][array[i]]
    return result

def backtrack(full, depth, first, visited, n, start):
    global answer
    if depth == full:
        second = []
        for i in range(n):
            if not visited[i]:
                second.append(i)
        answer = min(answer, abs(calculate(first) - calculate(second)))
        return
    for i in range(start, n):
        # first team 에 넣어
        if visited[i]:
            continue
        first.append(i)
        visited[i] = True
        backtrack(full, depth+1, first, visited, n, i)
        first.pop()
        visited[i] = False

def solution(n):
    first = []
    visited = [False] * n
    for i in range(2, n//2+1):  # first team 인원 수
        backtrack(i, 0, first, visited, n, 0)

if __name__ == "__main__":
    answer = int(1e9)
    N = int(sys.stdin.readline().rstrip())
    graph = []
    for _ in range(N):
        graph.append(list(map(int, sys.stdin.readline().rstrip().split())))
    solution(N)
    print(answer)