[알고리즘][Python] 백준 1007 벡터 매칭 문제 풀이

문제 출처 : www.acmicpc.net/problem/1007

1007번: 벡터 매칭

---

문제 해석 : N개의 좌표평면 상의 점이 주어졌을 때 N//2개의 벡터를 생성하고 이를 합한 길이의 최솟값을 구하라

 

문제 풀이 :  v1 = (x1-x2, y1-y2)이다. v2 = (x3-x4, y3-y4) 이다. 합벡터 v3 = v1-v2 = ( (x1-x2) - (x3-x4), (y1-y2) - (y3-y4) ) 이다. 즉 임의의 v3 = ( ( x1 + x3 ) - ( x2 + x4 ), ( y1 + y3 ) - ( y2 + y4 ) )으로 볼 수 있다. 이는 주어진 좌표에서 임의로 반을 선택하여 나머지 반을 뺀 것으로 볼 수 있기 때문에 itertools에 있는 combinations를 활용하여 풀이 할 수 있다.

---

풀이 코드

import math, sys, itertools
input = sys.stdin.readline

T = int(input())

for test_case in range(T):
    N = int(input())

    point = []
    total_x = 0
    total_y = 0

    for _ in range(N):
        x, y = list(map(int, input().split()))
        point.append([x,y])
        total_x += x
        total_y += y

    ret = sys.maxsize
    com = list(itertools.combinations(point, int(N/2)))
    com_len = int(len(com)/2)

    for element in com[:com_len]:
        element = list(element)

        x1_total = 0
        y1_total = 0
        for x1, y1 in element:
            x1_total += x1
            y1_total += y1

        x2_total = total_x - x1_total
        y2_total = total_y - y1_total

        ret = min(ret, math.sqrt((x1_total - x2_total) ** 2 + (y1_total - y2_total) ** 2))
    print(ret)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.