[python] 백준 1007 : 벡터 매칭

문제 링크
https://www.acmicpc.net/problem/1007

접근 1

처음 접근 방법은 그야말로 처참했다...
각 점마다 번호를 부여하고, i번 점에서 j번 점으로 가는 벡터를 n//2 개 만큼 뽑는 방법을 생각했다.

주어진 예제에서 첫 경우를 생각해보자.
0번 점 (-5,-5)
1번 점 (5,5)
2번 점 (5,-5)
3번 점 (-5,5) 라고 할 때

(0->1) (2->3)
(0->1) (3->2)
(0->2) (1->3)
(0->2) (3->1)
(0->3) (1->2)
(0->3) (2->1)

이러한 접근 방법은 O(N!)인 방법으로 N<=20인 이 문제에는 적합하지 않았다.

접근 2

결국 오래 고민하다가 방법이 떠오르지 않아 다른 블로그를 참고하였다.(https://nerogarret.tistory.com/21)

v1 = (x1-x2, y1-y2)
v2 = (x3-x4, y3-y4) 라고 할 때
v1 + v2 = ( (x1-x2) + (x3-x4) , (y1-y2) + (y3-y4) )
= ( (x1+x3) - (x2+x4) , (y1+y3) - (y2+y4) )으로 볼 수 있다.

즉 N 개의 점 중에서 더할 점의 집단과 뺄 점의 집단을 구해주면 되는 것이다.
N이 최댓값인 20일 때, 대략 C(20,10) = 184756 번 반복하므로 충분히 가능하다고 생각했다.

추가적으로 처음에 입력을 받을 때 x값을 모두 더한 xtotal과 y값을 모두 더한 ytotal을 정의해주어 더하는 집단과 빼는 집단을 쉽게 구할 수 있도록 했다.

import sys
import math
from itertools import combinations

sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()

T = int(input())
for _ in range(T):
    n = int(input())
    ps = [0 for _ in range(n)]
    xtotal, ytotal = 0, 0
    for i in range(n):
        x, y = map(int, input().split())
        xtotal += x
        ytotal += y
        ps[i] = (x, y)

    min_scala = 1000000
    for c in combinations(range(n), n // 2): # nC(n//2)

        xsum, ysum = 0, 0
        for i in c:
            xsum += ps[i][0] # i번 점의 x값 더해주기 
            ysum += ps[i][1] # i번 점의 y값 더해주기

        xsum -= xtotal - xsum # <- 더하는 집단 - 빼는 집단 == 더하는 집단 - (x총합 - 더하는 집단)
        ysum -= ytotal - ysum

        scala = math.sqrt(xsum ** 2 + ysum ** 2) #벡터 크기
        if min_scala > scala:
            min_scala = scala

    print(min_scala)

삶이 쉽지 않음을 알 수 있다.

정답 코드

같은 블로그의 글을 또 다시 참고하여, 조합의 절반만 봐도 된다는 사실을 알았다...!

import sys
import math
from itertools import combinations

sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()

T = int(input())
for _ in range(T):
    n = int(input())
    ps = [0 for _ in range(n)]
    xtotal, ytotal = 0, 0
    for i in range(n):
        x, y = map(int, input().split())
        xtotal += x  
        ytotal += y  
        ps[i] = (x, y)

    min_scala = 1000000
    comb = list(combinations(range(n), n // 2))
    for c in comb[: len(comb) // 2]:  # 조합은 어떨 때 절반만 봐도 됨

        xsum, ysum = 0, 0
        for i in c:
            xsum += ps[i][0] # i번 점의 x값 더해주기 
            ysum += ps[i][1] # i번 점의 y값 더해주기

        xsum -= xtotal - xsum # <- 더하는 집단 - 빼는 집단 == 더하는 집단 - (x총합 - 더하는 집단)
        ysum -= ytotal - ysum

        scala = math.sqrt(xsum ** 2 + ysum ** 2)
        if min_scala > scala:
            min_scala = scala

    print(min_scala)