[C++] 백준 1007 [벡터 매칭]

문제설명

2차원 평면상에 N개의 점이 있고 두 점씩 모두 이어서 벡터로 만든다.(N은 짝수)
총 N/2개의 벡터가 나오는데, 이 벡터의 합의 길이의 최솟값을 출력하면 된다.
벡터의 길이의 합이 아니라 벡터의 합의 길이인 것이 중요하다.

풀이방법

모든 벡터의 쌍을 만들어서 그 벡터들의 합을 구할 수 있나 생각해보자.(브루트포스)

위처럼 총 벡터의 개수는 \( \frac{20!}{10!} \) 이므로, 대략 6700억의 경우의 수가 나오므로 불가능하다.

그래서, 우리는 벡터합의 성질을 이용해서 경우의 수를 줄일 것이다.

20개의 점은 10개의 끝점 과 10개의 시작점으로 나뉘는데, 벡터의 합은 (끝점의 합 - 시작점의 합)이므로, 결국에 끝점 10개와 시작점 10개만 골라주면 된다.
이는 \( ^{20}C_{10} \)의 경우의 수를 가진다.

이는 충분히 브루트포스로 구현 가능하다.

조합 구현

조합은 백트래킹을 통해 구현한다.
아래 코드와 같이 구현하면 된다.

void com(int n, vector<int>& picked, int to_pick){
    if(to_pick == 0){
        com_result.push_back(picked);
    }
    int smallest = picked.empty() ? 0 : picked.back()+1;
    for(int i=smallest; i<n; i++){
        picked.push_back(i);
        com(n, picked, to_pick-1);
        picked.pop_back();
    }
}

부동소수점 정밀도

아래와 같이 작성하면 소수점 자리를 고정할 수 있다.

cout<<fixed;
cout.precision(12);

소스코드

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int N;

vector<pair<int, int> > coor;
vector<int> empty_vec;
vector<vector<int> > com_result;

void com(int n, vector<int>& picked, int to_pick){
    if(to_pick == 0){
        com_result.push_back(picked);
    }
    int smallest = picked.empty() ? 0 : picked.back()+1;
    for(int i=smallest; i<n; i++){
        picked.push_back(i);
        com(n, picked, to_pick-1);
        picked.pop_back();
    }
}

int main(){
    cout<<fixed;
    cout.precision(12);
    int T;
    cin >> T;
    while(T--){
        long long tot_x = 0, tot_y = 0;
        long long result = 9223372036854775807;
        cin >> N;
        coor = vector<pair<int, int> >(N);
        com_result.clear();
        empty_vec.clear();
        for(int i=0; i<N; i++){
            cin >> coor[i].first >> coor[i].second;
            tot_x += coor[i].first;
            tot_y += coor[i].second;
        }
        com(N, empty_vec, N/2);
        for(int i=0; i<com_result.size(); i++){
            long long sum_x = 0;
            long long sum_y = 0;
            for(int j=0; j<com_result[i].size(); j++){
                sum_x += coor[com_result[i][j]].first;
                sum_y += coor[com_result[i][j]].second;
            }
            long long result_x = sum_x - (tot_x - sum_x);
            long long result_y = sum_y - (tot_y - sum_y);
            result = min(result, result_x*result_x + result_y*result_y);
        }
        cout << (double)sqrt(result) << "\n";
    }
}