[백준]1007 벡터매칭 #벡터

1. 풀이

처음엔 N개의 점을 모두 사용하여 N/2개의 선분을 만들었을 때 선분의 합이 최소가 되는 경우를 구해야 한다고 생각했다.

따라서 nC2*n-2C2*n-4C2...*4C2*2C2의 경우를 생각했었다.

하지만 문제에서 요구하는것은 "벡터의합의 길이"이다.

​

즉 4개의 점 (x1,y1),(x2,y2),(x3,y3),(x4,y4) 가 있을 때

(x_a+x_b -x_c-x_d , y_a+y_b-y_c-y_d )의 길이의 최솟값을 구하면 된다.

​

따라서 모든점의 개수(N개)중 시작점의 개수(N//2)를 뽑는 경우(나머지는 자동으로 도착점이 된다)는

nCn//2 이므로 해당 경우를 완전탐색하면 답이 된다.

​

2.소스코드

import sys
from itertools import combinations
import math

T=int(input())
for t in range(T):
    N=int(input())
    L=[]
    for i in range(N):
        L.append(list(map(int,sys.stdin.readline().rstrip().split())))
    #출발점
    comb=list(combinations([i for i in range(N)],N//2))
    ans=9876543210
    for starts in comb:
        fins=[i for i in range(N)]
        for s in starts:
            fins.remove(s)
        startX=sum([L[starts[i]][0] for i in range(N//2)])
        startY=sum([L[starts[i]][1] for i in range(N//2)])
        finX=sum([L[fins[i]][0] for i in range(N//2)])
        finY=sum([L[fins[i]][1] for i in range(N//2)])
        temp=math.sqrt((startX-finX)**2+(startY-finY)**2)
        if temp<ans:
            ans=temp
    print(ans)