[백준 1007] 벡터 매칭 (파이썬 / Python)

---

📑 문제

문제링크 : 벡터 매칭

---

🤔 생각의 흐름

고등학교 때 배웠던 벡터를 생각해봅시다. 벡터는 $\vec {AB} = B - A$ 로 표현할 수 있으며, 벡터 2개의 합은

\[\vec {AB} + \vec {CD} = (B - A) + (D - C)\] \[= (B + D) - (A + C)\tag{1}\] \[= (A + B + C + D) - 2 (A + C)\tag{2}\]

으로 표현할 수 있습니다. 즉, 모든 점을 더한 뒤 2 * (두 점의 합) 을 빼주는 것으로 두 벡터의 합을 구할 수 있습니다.

잠깐! 그냥 1 번 식처럼 (절반의 점들의 합) - (나머지 점들의 합) 으로 구하면 안되나요?

1번 식으로 풀어도 됩니다만, 코딩을 하다보니 2번 식으로 구현하는게 더 수월하더라구요.

이제 문제에 대해 생각해봅시다. $N \leq 20$ 이므로 점들은 최대 20개입니다. ans = min((N 개의 점들을 더한 값) - 2 * (N/2 개의 점들을 더한 값)) 으로 생각할 수 있겠네요. 그리고 N 개의 점들 중 N/2 개의 점을 선택하는 횟수는 ${N \choose N/2}$ 입니다.

---

🎯 풀이방법

수학, Brute Force 문제입니다.

x, y : 점들의 x 좌표와 y 좌표를 저장하는 리스트

tx, ty : 입력받은 x 좌표와 y 좌표들의 합

combi(cnt, idx, sx, sy) : 벡터 합의 길이의 최솟값을 ans 에 저장하는 재귀함수

• cnt : N / 2 개의 점을 선택하는데 남은 점들의 갯수
• idx : 몇 번 째 점들부터 선택해야 하는지.
• sx, sy : 선택한 점들의 합

1. 점을 입력받으며 x 좌표와 y 좌표의 총합을 구합니다.

2. 재귀함수(combi 함수)를 이용하여 N/2 개의 점들을 선택하여 선택한 좌표들의 합을 구합니다.

3. (점들의 총합) - (선택한 점들의 합) 을 구하여 벡터의 길이를 구합니다. 구한 길이가 ans 보다 작다면 ans 를 갱신합니다.

4. 선택할 수 있는 모든 경우를 선택한 후의 ans 를 출력해줍니다.

---

🔎 유의할 점

• 구해야하는 것은 벡터 길이의 합이 아닌 벡터 합의 길이입니다.

---

💻 코드

from sys import stdin

input = stdin.readline


def solve():
    TC = int(input())
    inf = float('inf')
    x, y = [0] * 20, [0] * 20
    ans, tx, ty = inf, 0, 0

    def combi(cnt, idx, sx, sy):
        nonlocal ans
        if cnt == 0:
            tmp = ((tx - 2 * sx) ** 2 + (ty - 2 * sy) ** 2) ** 0.5
            if tmp < ans:
                ans = tmp

        else:
            for i in range(idx, N - cnt + 1):
                combi(cnt-1, i+1, sx+x[i], sy+y[i])

    for _ in range(TC):
        N = int(input())
        ans, tx, ty = inf, 0, 0
        for i in range(N):
            x[i], y[i] = map(int, input().split())
            tx += x[i]
            ty += y[i]
        combi(N//2 - 1, 1, x[0], y[0])
        print(ans)


if __name__ == '__main__':
    solve()