백준 1007번 문제 - 벡터 매칭

---

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

벡터 매칭 문제는 다음의 조건을 염두에 두고 생각하여 풀 수 있는 문제이다.

• 모든 점은 한 번씩 쓰여야 함
• 벡터를 구성하는 것은 두 점

(x1, y1), (x2, y2)의 두 점으로부터 형성되는 벡터는 (x1-x2, y1-y2) 또는 (x2-x1, y2-y1)의 형태를 갖는다.

따라서 N개의 점으로 구성된 집합으로부터 얻을 수 있는 벡터 합의 크기는 N/2개의 점을 -연산, 나머지 점을 +연산하여 합한 벡터 x,y의 크기로서 표현된다.

중복 없이, N개의 점에서 N/2개의 점을 선택하므로 ${N}\choose{\frac{N}{2}}$의 경우의 수가 존재하지만 N은 20 이하의 자연수라는 조건이 존재하므로 재귀함수로 모든 점을 +한 결과와 -한 결과의 비교를 통해서 최소 값을 구하여 풀 수 있다.

또한 (x1-x2, y1-y2)의 길이와 (x2-x1, y2-y1)의 길이는 모두 $\sqrt{(x1-x2)^2+(y1-y2)^2}$으로 같으므로 첫번째 점을 +연산으로 가정하여 풀어도 첫번째 점을 -연산하여 계산한 최소값과 동일한 결과를 얻을 수 있다.

#include<iostream>
#include<math.h>
using namespace std;
#define MAXSIZE 21
int T,N;
int x[MAXSIZE],y[MAXSIZE],c[MAXSIZE];//배열 c: +연산시 1, -연산시 -1
double result;

void combination(int n,int index){ 
    if(index==N) return;
    if(n==N/2){ //-연산을 할 점을 모두 결정하였다면 벡터 합의 크기를 계산하여 비교
        double sum_x=0,sum_y=0;
        for(int i=0;i<N;i++){
            sum_x += c[i]*x[i]; //벡터 합의 x좌표
            sum_y += c[i]*y[i]; //벡터 합의 y좌표
        }
        double temp = sqrt((sum_x*sum_x)+(sum_y*sum_y));
        if(temp<result) result = temp;
        return;
    }
    combination(n,index+1); //다음 인덱스에 대해 +연산을 한 결과로 비교
    c[index]=-1;
    combination(n+1,index+1);   //다음 인덱스에 대해 -연산을 한 결과로 비교
    c[index]=1;
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d,",&N);
        result=1.79E+308;   //다른 테스트 케이스에 대해 영향을 미치지 않도록 초기화
        for(int i=0;i<N;i++){
            scanf("%d %d",&x[i],&y[i]);
            c[i] = 1;   //모든 점을 +연산 상태로 초기화하여 계산
        }
        combination(0,0);
        printf("%f\n",result);
    }
    return 0;
}