#1007 벡터 매칭(Mathematics)

이 문제는 Gold II 문제입니다.  처음에는 동적 프로그래밍을 이용한 TSP프로그램인 줄 알고 열심히 짰다가, 예제 결과가 틀렸길래 뭐지 하고 봤었네요.  제가 문제를 풀 때만 해도 Gold I 문제였는데, 그동안 난이도가 떨어졌네요.

 

어쩐지 벡터 매칭이 문제 이름인데, TSP 문제일리가 없었죠.  그리고 TSP 문제였다면 조금 더 난이도 값이 주어졌을 것 같네요.  TSP 문제였다면, 비트매스킹을 써서 동적 프로그래밍으로 답을 해야하죠.  그 귀찮은 프로그래밍을 다 했었는데.  최대 점들의 갯수가 20개이므로, TSP 문제였다고 해도 시간안에 대충 풀었을 듯 합니다.

 

 

문제는 2차원 공간상에 점들이 주어지면, 이 점들중 두개씩 짝을 이루어 벡터를 만들었을 때, 그 벡터들의 합이 최소가 되도록 하는 것입니다.

 

문제는 아래의 링크입니다.

https://www.acmicpc.net/problem/1007

1007번: 벡터 매칭

 

이 문제에서 중요한 것은 점들 중 절반은 더하기를 나머지 절반은 빼기를 한 결과의 길이값이 가장 적도록 하면 됩니다.

가장 무식한 방법으로 풀어보자면, 순회를 하면서 절반을 선택하는 방법입니다.  최대 점들의 갯수는 20개이므로, 20개중 10개를 선택하는 경우의 수가 너무 크지 않으면 됩니다.

 

\[ \binom{20}{10} = 184,756 \]

 

10만 단위의 경우의 수이면 테스트 케이스가 몇천 단위가 아닌 이상 시간안에 들어오는 경우의 수입니다.  AC를 받을 때 48ms 받았습니다.  더 좋은 결과를 낸 사람들도 많네요.

 

이 문제는 \(V_i + V_j\) 를 하게 되면, 각각의 벡터의 크기를 합하면 됩니다.  그래서 20개중에 10개의 점은 더하고, 10개의 점은 빼서 최종적으로 얻어진 벡터의 길이를 구하면 됩니다.

 

다음은 제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------
//  baekjoon #1007 - Vector Matching
//    - by Aubrey Choi
//    - created at 2019-12-29
//----------------------------------------------------------
#include <stdio.h>
#include <math.h>

int n, x[20], y[20];
double getOpt(int c, int p, int m, int xs, int ys)
{
  if(c==n) return sqrt((double)xs*xs+(double)ys*ys);
  double min=1e10, r;
  if(p<n/2) { r=getOpt(c+1, p+1, m, xs+x[c], ys+y[c]); min=(r<min)?r:min; }
  if(m<n/2) { r=getOpt(c+1, p, m+1, xs-x[c], ys-y[c]); min=(r<min)?r:min; }
  return min;
}
int main()
{
  int t, i, j;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d%d",x+i,y+i);
    printf("%.8lf\n", getOpt(0, 0, 0, 0, 0));
  }
}