백준 #1007 벡터 매칭 (파이썬)

오늘의 한 마디
굳이 문제를 '그대로' 구현할 필요는 없는 법!
이 문제에서도 진짜 일일이 N!개를 다 매칭시킬 필요는 없었다.

• Baekjoon 문제 링크
• solved.ac > 문제 > CLASS 5에 수록된 문제입니다.

문제

평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다.

벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반이다.

평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

테스트 케이스의 첫째 줄에 점의 개수 N이 주어진다. N은 짝수이다. 둘째 줄부터 N개의 줄에 점의 좌표가 주어진다. N은 20보다 작거나 같은 자연수이고, 좌표는 절댓값이 100,000보다 작거나 같은 정수다. 모든 점은 서로 다르다.

출력

각 테스트 케이스마다 정답을 출력한다. 절대/상대 오차는 10-6까지 허용한다.

예제 입력 1

2
4
5 5
5 -5
-5 5
-5 -5
2
-100000 -100000
100000 100000

예제 출력 1

0.000000000000
282842.712474619038

예제 입력 2

1
10
26 -76
65 -83
78 38
92 22
-60 -42
-27 85
42 46
-86 98
92 -47
-41 38

예제 출력 2

13.341664064126334

---

발상

문제를 처음에 읽고는, 무슨 말인가 했다.

1. N개의 점을 두개씩 짝짓는다.
2. 각각의 페어를 (y2-y1, x2-x1)로 하여 벡터를 만든다.
3. 만든 N//2개의 벡터를 모두 합한다.
4. 합한 최종 벡터의 norm을 구한다.

여러개의 짝짓는 경우 중에서 norm의 최솟값은?
이렇게 이해할 수 있겠다.

진짜 짝 지을 생각하니까, 벌써 시간복잡도 때문에 머리가 어지럽다.

1. 임의로 1번 점을 정해서, 그 1번 점이 페어를 선점한다. (N-1개 중에)
2. 임의로 2번 점을 정해서, 그 2번 점이 페어를 선점한다. (N-3개 중에)
   ...

이런 식으로 가면, (N-1)(N-3)(N-5)... 이런 식으로 O(N!)가 나올 것으로 예상되었다.

이제까지 코딩테스트를 풀면서, O(N!)과 O(2^N) 시간복잡도가 나오는 경우에는, 답인 적이 한번도 없었다. 커봐야 O(N^3)이었다.

---

이 링크를 보고 발상을 얻었다.

당연히 순열을 쓸 것 같은 이 문제에서, 조합을 썼다는 사실이 매우 신박했다. .

내가 이해한 내용은 다음과 같다.

1. 두 점을 매칭(= y2-y1, x2-x1)하여 만든 벡터를 모두 더한 합을 구하자!
2. 최솟값만 찾으면 되니까, 굳이 점끼리 꼬이면서 만드는 순열까지 고려할 필요 없음
3. 조합으로 N//2개 고른 다음, 나머지 N//2개의 점과 어떻게든 일대일대응됐다고 치고,
4. 벡터의 합의 norm이기 때문에, (선택받은 y의 합-나머지 y의 합, 선택받은 x의 합-나머지 x의 합) 벡터의 norm을 구하면 된다.

사실 구체적으로 어떤 점과 어떤 점이 연결되었는지는 중요하지 않았다.
출발점과 도착점 그룹이 같기만 하다면, 벡터를 모두 더해 만든 벡터는 모두 같은 벡터이기 때문이다.

---

풀이

import sys
import itertools
import math

T = int(sys.stdin.readline().rstrip())
for _ in range(T):
    N = int(sys.stdin.readline().rstrip())
    points = []
    y_total, x_total = 0, 0
    for _ in range(N):
        y, x = map(int, sys.stdin.readline().rstrip().split())
        points.append((y, x))
        y_total += y
        x_total += x

    answer = float('inf')
    for case in itertools.combinations(range(N), N//2):
        y_sum, x_sum = 0, 0
        for idx in case:
            y, x = points[idx]
            y_sum += y
            x_sum += x
            
        y_remain = y_total - y_sum
        x_remain = x_total - x_sum
        
        norm = math.sqrt((y_sum-y_remain)**2 + (x_sum-x_remain)**2)
        answer = min(answer, norm)
        
    print(answer)