[BOJ, 백준] 1007 벡터매칭 Python

 

 

문제는 다음과 같다

 

해답 코드는 다음과 같이 나오겠다.

 

이 문제에서 중요하다고 느껴지는 것은, 포함된 벡터들의 "합"의 크기의 최솟값인 점이 되겠다.

주어진 좌표가 (x1,y1) , ... , (x_2n, y_2n) 이러한 형식으로 주어져있다면

initial point들의  좌표를 (nx_1, ny_1) , ... , (nx_n, ny_n)로 둘 수 있겠고

terminate point들의 좌표를 (mx_1,my_1), ..., (mx_n, my_n)으로 둘 수 있겠다.

 

이렇게 좌표를 나누는 것이 가능했을 때, 이곳의 벡터들의 합은 항상 고정되는 것을 알 수 있다. 

(nx_1, ny_1)이 (mx_1, my_1), ... , (mx_n, my_n) 중 하나로 매칭되어서 (mx_k1, my_k1)과 매칭 되었을 때  얻어지는 벡터는

(mx_k1 - nx_1 , my_k1 - ny_1)꼴이다.

같은 방식으로 (nx_2, ny_2)는 (mx_1, my_1), ...  (mx_(k1 -1), my_(k1 - 1)),  (mx_(k1 + 1), my_(k1 + 1))... , (mx_n, my_n) 중 하나로 매칭되어서 얻어지는 벡터는

(mx_k2 - nx_2, my_k2 - ny_2) 꼴이 되겠다.

반복해서 진행하면 전부 일대일로 매칭되겠고

결국 벡터 성분의 합은

(mx_1 + ... + mx_n - nx_1 - ... - nx_n, my_1 + ... + my_n -  ny_1 - ... - ny_n) 꼴로 일의적 (uniquely)하게 주어지는 것을 알 수 있겠다.

 

이 성질을 활용하면 알고리즘을 짜본다면 다음과 같이 얻어질 수 있겠다.

import sys
import math
from itertools import combinations

T = int(input())
for _ in range (0,T):
    num_pt = int(input())
    pts = []
    sum_x, sum_y = 0, 0
    for _ in range (0,num_pt):
        a,b = map(int,input().split())
        sum_x += a
        sum_y += b
        pts.append([a,b])
    initial = list(combinations(pts, num_pt // 2))
    answer = int(1e9)
    for init_pt in initial:
        init_pt = list(init_pt)
        ini_x, ini_y = 0, 0
        for pt in init_pt:
            ini_x += pt[0]
            ini_y += pt[1]
        ter_x, ter_y = sum_x - ini_x , sum_y - ini_y
        answer = min(answer, math.sqrt((ter_x - ini_x) ** 2 + (ter_y - ini_y) ** 2))
    print(answer)