[백준] 벡터 매칭

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

1007번: 벡터 매칭

한참의 고민 끝에 풀은 문제입니다. 벡터라는 말에 너무 쫄았던 것 같습니다. 벡터를 만들기 위해서 2가지를 선택하여 한쪽에서 나머지를 빼준 다음 만들어진 벡터의 합을 구하기 위해 x, y를 모두 합쳐야합니다. 예를 들어 (x1, y1), (x2, y2), (x3, y3), (x4 y4)가 있을 때 (x1 - x2, y1 - y2), (x3 - x4, y3 - y4) 2개의 벡터를 만들 수 있고 이들의 합은 (x1 + x3 - x2 - x4, y1 + y3 - y2 - y4)가 되게 됩니다. 결론적으로 nCn/2개를 뽑아서 더하고 나머지 nCn/2를 빼주면 x, y를 구해줄 수 있습니다. 각각의 조합에서 얻을 수 있는 벡터 합의 길이를 계산하여 최소값을 구해주면 됩니다.

 

import sys, math
from itertools import combinations

INT_MAX = sys.maxsize
#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    n = int(input())

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

    candi = combinations(range(n), n // 2)
    ans = INT_MAX

    for combi in candi:
        isPlus = [False] * n

        for idx in combi:
            isPlus[idx] = True

        x = 0
        y = 0

        for i in range(n):
            if isPlus[i]:
                x += points[i][0]
                y += points[i][1]
            else:
                x -= points[i][0]
                y -= points[i][1]

        ans = min(ans, math.sqrt(x ** 2 + y ** 2))

    print(ans)