[BaekJoon] 1007: 벡터 매칭

BaekJoon 1007: 벡터 매칭

풀이 방법

집합 P는 n개의 점들의 집합이고, P의 벡터 매칭은 P의 모든 점을 한 번씩 사용하여 만든 벡터의 집합이다. 즉,

$P = {(x_1, y_1), (x_2, y_2), \dots , (x_n, y_n)}$

$VM = {(x_i - x_j,\space y_i - y-j)\space|\space 1 \le i, j \le n, i \ne j }$

 

따라서 벡터 매칭에 속하는 모든 벡터의 합은 다음과 같이 구할 수 있다.
$v_1 = (x_2 - x_1, \space y_2 - y_1)$
$v_2 = (x_4 - x_3, \space y_4 - y_3)$
$ \dots $
$v_{n/2} = (x_n - x_{n-1}, \space y_n - y_{n-1})$

$v_1 + v_2 + ... + v_{n/2} =
((x_2 + x_4 + ... + x_n) - (x_1 + x_3 + ... + x_{n-1}),\space
(y_2 + y_4 + ... + y_n) - (y_1 + y_3 + ... + y_{n-1}))$

$v_1 + v_2 + ... + v_{n/2} =
\sum_{k=1}^n x_k - 2\sum_{k=1}^n x_{2k-1},\space
\sum_{k=1}^n y_k - 2\sum_{k=1}^n y_{2k-1})$

 

이때 가능한 벡터 매칭의 가짓수는 집합 P에서 $N/2$ 개의 출발점을 선택하는 경우의 수와 같으므로, 해당 경우를 모두 탐색하여 벡터합의 길이의 최솟값을 찾아 문제를 해결할 수 있다. 따라서 Brute Force로 탐색해야 하는 경우의 수는 최대 $nC{n/2}$ 이다.

 

다음과 같은 방법으로 간단한 알고리즘을 작성해 볼 수 있다.

1. 집합 P의 모든 점에 대해 x좌표끼리, y좌표끼리 각각 더한 값을 저장한다.
2. 집합 P에서 벡터의 출발점에 해당하는 N/2개의 점을 선택하는 모든 경우의 수를 리스트에 저장한다.
3. 2에서 저장된 모든 경우의 수에 대해, 해당 경우에서 발생하는 벡터 합의 길이를 연산해 이전의 최솟값과 비교하여 더 작을 경우 최솟값을 갱신한다. 벡터 합은 1에서 저장된 x좌표, y좌표의 총합에서 출발점의 x좌표 합,y좌표 합을 두 번씩 빼서 계산한다.
4. 2에서 저장된 모든 경우의 수 탐색이 종료되면 최솟값을 출력한다.

시행착오

• 문제를 정확히 이해하는 데 시간이 꽤 걸렸다. 처음에는 집합 P에서 만들어질 수 있는 모든 벡터를 구하고자 했는데, 벡터의 개수가 점의 개수의 절반이라는 점을 제대로 체크했다면 보다 빠르게 풀이할 수 있지 않았나 싶다.
• 첫 번쨰 접근에서는 팩토리얼 수준의 시간 복잡도가 나왔으나.. 대부분의 문제는 팩토리얼 알고리즘을 1순위 해결책으로 두지 않는다는 사실을 잘 기억해야 한다. 출발점을 선택하면 (모든 점을 한 번씩 사용해야 하므로) 도착점도 자동으로 선택된다는 점이 키포인트였다.

전체 코드

from itertools import combinations
import math

T = int(input())

for _ in range(T):
    N = int(input())
    P = [(0, 0) for _ in range(N)]
    xsum, ysum = 0, 0

    for i in range(N):
        x, y = map(int, input().split())
        xsum += x
        ysum += y
        P[i] = (x,y)

    cases = list(combinations(P, N // 2))
    min = -1

    for case in cases:  # NC(N/2)
        vsum = [xsum, ysum]

        for point in case:
            vsum[0] -= (2 * point[0])
            vsum[1] -= (2 * point[1])

        length = math.sqrt(pow(vsum[0], 2) + pow(vsum[1], 2))

        if (length < min or min < 0):
            min = length

    print(min)