[백준] 1007번: 벡터 매칭 (수학) c++ 풀이

접근:

우선 모든 벡터의 조합을 계산 해보면, 

최대 C(20*19, 10) 인데 기하급수적인 크기의 수이다.

여기서 접근은 벡터의 덧셈 뺄셈의 성질을 이해하는 것이 중요하다.

벡터는 시작점과 종점으로 이루어져 있는데, 예를 들어 두 점을 (a,b) (c,d) 라고 하면,

벡터 v는 v = (c-a, d-b) = (c,d) - (b,a) 라고 표현 할 수 있다.

모든 벡터의 합은 v1+v2+...+vn = {(c1,d1)+(c2,d2) + ... + (cn ,dn)} - {(b1,a1) + (b2,a2) + ... + (bn, an)} 라고 볼 수 있다.

모든 점을 한 번씩 사용해야 하므로, 점이 n개가 있다면

n/2개의 점을 선택해서 다 더한 것에 남은 점들을 다 뺀 것과 같다.

이렇게 된다면, 최악의 경우 C(20,10) 의 조합으로 줄일 수 있게 된다.

 

전략:

브루트 포스 하게 모든 경우의 수를 구해야한다.

모든 경우의 수를 dfs를 이용하여 n/2개를 선택하도록 하여(백트래킹), 선택한 것을 토대로 벡터를 구해 길이를 구하고,

각 경우마다 이전 최소값과 비교하여 최소값을 갱신한다.

구현:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int tc, n;
int x, y;
pair<int,int> dot[21];

pair<int,int> group1;
pair<int,int> group2;
double min_length =1000000000.0;
bool visit[21]{};

double length(){
    group1 = group2 = {0,0};

   for(int i=0;i<n;i++){
       if(visit[i]){
            group1.first += dot[i].first;
            group1.second += dot[i].second;
       }else{
            group2.first += dot[i].first;
            group2.second += dot[i].second;
       }
   }  
    return sqrt(pow(group1.first-group2.first,2) + pow(group1.second-group2.second,2));
}

void dfs(int remain, int startidx){
    if(remain == 0){
        double len = length();

        if(min_length > len){
            min_length = len;
        }
    }else{
        for(int i=startidx;i<n;i++){
            if(!visit[i]){
                visit[i] = true;
                dfs(remain-1,i);
                visit[i] = false;
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> tc;
    for(int test=0;test<tc;test++){
        cin >> n;
        min_length =1000000000.0;
        for(int i=0;i<n;i++){
            cin >> dot[i].first >> dot[i].second; // first: x, second:   
        }
        dfs(n/2, 0);
        cout << fixed;
        cout.precision(7);
        cout << min_length << '\n';
    }
    return 0;
}