[백준] 벡터 매칭

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

1007번: 벡터 매칭

우선 문제부터 간단하게 요약하면,

 

점들이 N(짝수) 개 찍혀 있고, 이 점들을 둘씩 이으면 벡터가 생기게 됩니다. 이런 벡터들의 합의 최솟값을 구하는 문제입니다.

 

<Solution>

어렵게 생각하지 말고, 벡터의 합은 각각의 성분들을 더하면 되는 것을 생각해봅시다. 

 

만약 <1,2> <3,4> 이렇게 두개의 벡터가 있다면, 벡터의 합은 <4,6>이 되고 이 길이가 우리가 구하는 벡터의 합의 길이입니다. 한마디로, N개의 점들중 시작점 N/2개를 뽑아 벡터를 구성한뒤, 벡터의 합을 구하고 그중 최솟값을 구하면 됩니다.

 

N개의 점들중 N/2개의 점을 뽑는 것은 조합입니다. 조합은 일반적으로 python과 같은 언어에는 내장되어 있지만, c++의 경우 dfs로 구현합니다. 이렇게 단순한 조합은 binary tree를 이용한 조합으로 구현하는 것이 간편하고 이렇게 구현한 조합에 각각의 경우에 대해 길이를 구할 수 있도록 하면 됩니다.

 

가지치기는 만약 남은 것들을 모두 뽑아도, N/2 개를 뽑지 못하는 경우에 대해 진행하면 됩니다.

 

실제 구현은 아래와 같습니다.

 

#include <iostream>
#include <cmath>
#include <climits>

using namespace std;

int T; int N;

struct dot{
    int x;
    int y;
};

dot dots[25];
int index_array[25];

double ans;

double calculate_dist(){
    int left_sum_x = 0;
    int left_sum_y = 0;
    int right_sum_x = 0;
    int right_sum_y = 0;
    for(int i = 0; i<N; i++){
        if(index_array[i]){
            left_sum_x += dots[i].x;
            left_sum_y += dots[i].y;
        }
        else{
            right_sum_x += dots[i].x;
            right_sum_y += dots[i].y;
        }
    }
    return sqrt(pow(left_sum_x - right_sum_x,2) + pow(left_sum_y - right_sum_y, 2));
}


// combination using binary tree
void dfs(int step, int how_many_seleted){
    // when will it return 
    if(step == N || how_many_seleted == N/2){
        if(!(how_many_seleted == N/2)) return;
        ans = min(ans, calculate_dist());
        return;
    }

    // 발전 포기 (다음 모든걸 골라도 N/2개 못고를 때)
    if(how_many_seleted + (N - step) < N/2){
        return;
    }

    // 현재 step 고르는 경우
    index_array[step] = 1;
    dfs(step+1, how_many_seleted+1);
    index_array[step] = 0;

    // 현재 step 고르지 않는 경우
    dfs(step+1, how_many_seleted);
    
    return;
}


int main(){
    cin >> T;

    for(int i = 0; i<T; i++){
        // solve for each testcase
        cin >> N;

        // get input
        for(int j = 0; j<N; j++){
            cin >> dots[j].x >> dots[j].y;
        }

        // solve by using dfs
        ans = numeric_limits<double>::max();
        dfs(0, 0);
        cout << fixed;
        cout.precision(12);
        cout << ans << endl;
    }
}