[백준] 1007번: 벡터 매칭, 시간 초과의 늪

시간 초과의 늪에 빠져 결국 다른 분의 코드를 보았다.ㅠㅠ

처음에는 2개씩 짝을 짓는 dfs(재귀)로 풀어보고자 했다.

# 2개씩 N/2의 쌍을 만들어서 풀이.
import sys
input = sys.stdin.readline

T = int(input())


def add_vector(a, b):
    return (a[0] + b[0], a[1] + b[1])


def make_vector(i, j):
    dot_a, dot_b = dots[i], dots[j]
    return (dot_b[0] - dot_a[0], dot_b[1] - dot_a[1])


def get_distance(v):
    return (v[0]**2 + v[1]**2)**(1 / 2)


def dfs(is_selected, cur, cnt, v):
    global N, min_sum_vector
    # 모두 선택되었을 경우
    if cnt == N:
        min_sum_vector = min(min_sum_vector, get_distance(v))
        return
    i = is_selected.index(False, cur, N)
    is_selected[i] = True
    for j in range(i + 1, N):
        if not is_selected[j]:
            is_selected[j] = True
            v_x, v_y = make_vector(i, j)
            dfs(is_selected, i + 1, cnt + 2, add_vector(v, (v_x, v_y)))
            dfs(is_selected, i + 1, cnt + 2, add_vector(v, (-v_x, -v_y)))
            is_selected[j] = False
    is_selected[i] = False
    return


for _ in range(T):
    N = int(input())
    dots = [list(map(int, input().split())) for _ in range(N)]
    min_sum_vector = int(1e9)

    dfs([False] * N, 0, 0, (0, 0))
    print(min_sum_vector)

그러나 시간 초과가 나서, N/2개의 숫자를 먼저 뽑는 방식으로 다시 풀어보았다. 또한 벡터의 합을 구하는 데, 몇가지 특징이 있어 그것도 함께 적용해 보았다.
참고 https://nerogarret.tistory.com/21

# 2개씩 N/2의 쌍을 만들어서 풀이.
import sys
from itertools import combinations

input = sys.stdin.readline


def distance(a):
    return (a[0]**2 + a[1]**2)**(1 / 2)


T = int(input())

for _ in range(T):
    N = int(input())
    dots = []
    total_sum_vector = [0, 0]
    min_sum_vector = int(1e9)

    # 모든 점 다 더하기
    for _ in range(N):
        a, b = map(int, input().split())
        dots.append([a, b])
        total_sum_vector[0] += a
        total_sum_vector[1] += b

    # 출발점 N/2 개 채택
    for selected_dots in list(combinations(range(0, N), N // 2)):
        start_sum_vector = [0, 0]
        for dot in selected_dots:
            start_sum_vector[0] += dots[dot][0]
            start_sum_vector[1] += dots[dot][1]

            cur_sum_vector = (total_sum_vector[0] - start_sum_vector[0] * 2,
                              total_sum_vector[1] - start_sum_vector[1] * 2)
            min_sum_vector = min(min_sum_vector, distance(cur_sum_vector))
    print(min_sum_vector)

그러나 이 코드도 시간 초과..ㅠㅠ 다른 분 코드랑 비교해보니, 다른 점은 숫자의 합을 구할때 나는 배열의 0번 인덱스, 1번 인덱스에 들어있는 수에 계속 더한다는 것이었고 다른 분은 그냥 2개의 변수에 따로 더한다는 점이 었다...
그 부분을 수정해서 적용하니.. 바로 통과..

# 2개씩 N/2의 쌍을 만들어서 풀이.
import sys
from itertools import combinations
input = sys.stdin.readline


def distance(a):
    return (a[0]**2 + a[1]**2)**(1 / 2)


T = int(input())

for _ in range(T):
    N = int(input())
    dots = []
    x_sum = 0
    y_sum = 0
    total_sum_vector = [0, 0]
    min_sum_vector = int(1e9)

    # 모든 점 다 더하기
    for _ in range(N):
        a, b = map(int, input().split())
        dots.append([a, b])
        x_sum += a
        y_sum += b

    # 출발점 N/2 개 채택
    for selected_dots in list(combinations(dots, N // 2)):
        start_x_sum = 0
        start_y_sum = 0
        for x, y in selected_dots:
            start_x_sum += x
            start_y_sum += y

        cur_sum_vector = (x_sum - start_x_sum * 2,
                              y_sum - start_y_sum * 2)
        min_sum_vector = min(min_sum_vector, distance(cur_sum_vector))
    print(min_sum_vector)

다음부터는 고려해서 짜보아야겠다..!