[C++] 1007번 벡터 매칭

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

---

 

24/12/26

 

 

약간의 아이디어가 필요한 브루트포스 문제이다. $N$의 제한이 $20$으로 수상하게 작은데, 어떻게 하면 효율적으로 탐색할 수 있는지를 고민하면 해결할 수 있다.

---

 

문제 접근 방식:

 

 

시작 점과 끝 점을 정해서 이음으로써 하나의 벡터를 만들 수 있다.

 

이렇게 해서 $N$개의 점으로 $N/2$개의 벡터를 만들 수 있는데, 이 벡터들의 합의 길이의 최솟값을 구하는 것이 문제의 목적이다.

 

$N$의 제한이 $20$으로 수상하게 작은 것을 쉽게 관찰할 수 있는데, 효율적으로 브루트포스를 해야함을 확인할 수 있다.

 

시작 점 $S$과 끝 점 $E$로 이루어진 하나의 벡터 $\mathbf{V}$가 주어지면, 이 벡터는 시작 점이 $O$이고, 끝 점이 $S$인 벡터 $\mathbf{A}$와 시작 점이 $O$이고 끝 점이 $E$인 벡터 $\mathbf{B}$로 표현될 수 있다.

 

$$\mathbf{V} = \mathbf{B} - \mathbf{A}$$

 

이를 이용해보자.

 

예를 들어, 점이 8개 있다고 하면 벡터 $\mathbf{V}$가 4개 만들어 질 것이다. $\mathbf{V}_{1}, \mathbf{V}_{2}, \mathbf{V}_{3}, \mathbf{V}_{4}$ 총 $4$개가 있다고 하자.

 

그러면 이에 해당하는 $\mathbf{A}_{i}$와 $\mathbf{B}_{i}$가 존재할 것이다.

 

이를 다 더하면 다음과 같다.

 

$$\sum \mathbf{V}_{i} = \sum \mathbf{B}_{i} - \sum \mathbf{A}_{i}$$

 

$\mathbf{A}$에 속하는 점은 총 $4$개이므로, ${8 \choose 4}$가지의 경우의 수만 고려하면 충분하다.

 

편의 상 모든 점을 더한 벡터를 $\mathbf{T}$라고 하면, 우리의 목적은 다음을 구하는 것과 동일한 목적으로 바뀌게 된다.

 

$$\min (\lvert \mathbf{T} - 2 \sum \mathbf{A}_{i} \rvert)$$

 

따라서, 점들의 리스트가 주어지면 그 중에서 $N/2$개를 선택하는 백트래킹 함수를 구현하고, 그 함수 내에서 주어진 값을 계산한 뒤, 최솟값을 갱신하는 식으로 구현하면 충분하다.

 

물론 백트래킹 안쓰고 그냥 next_permutation써서 조금 쉽게 구할 수도 있고, 비트마스킹을 써서 주어진 크기의 조합만 탐색하는 방법도 가능하다. 후자는 $\mathcal{O}(2^{n})$의 시복도가 소요되겠지만(실제 실행은 주어진 크기가 만족되었을 때만 되기 때문에 시복도에 비해 실행시간이 더 짧을 수 있다.)...

 

왜 C++에서는 파이썬처럼 combinations가 없을까

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 1007번 벡터 매칭
// 수학, 브루트포스
/*
접근 방법:
일단 N개의 점을 2개의 세트로 분리하자. A세트/B세트
두 세트의 크기는 동일하다. 하나의 점은 O에서 시작해서 그점으로 끝나는 벡터로 간주할 수 있다.
임의의 벡터 V = Bi-Ai로 쓸 수 있으므로, (B세트의 합) - (A세트의 합)의 최솟값이 문제에서 요구하는 답이다.
즉, 전체 벡터의 합을 T라고 하면, min(Norm(T-2*(choose_sum)))이 문제의 요구 사항이다.
*/
#include <iostream>
#include <vector>
#include <cmath> // sqrt
#include <iomanip> // setprecision
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'

pair<int, int> operator+(const pair<int, int>& p1, const pair<int, int>& p2){
    return {p1.first+p2.first, p1.second+p2.second};
}

pair<int, int> operator-(const pair<int, int>& p1, const pair<int, int>& p2){
    return {p1.first-p2.first, p1.second-p2.second};
}

pair<int, int>& operator+=(pair<int, int>& p1, const pair<int, int>& p2){
    p1.first += p2.first; p1.second += p2.second;
    return p1;
}

double norm(const pair<int, int>& vec){
    return sqrt((double)(((long long)vec.first * (long long)vec.first) + ((long long)vec.second * (long long)vec.second)));
}

void dfs(vector<bool>& check, vector<pair<int, int>>& group_A, const vector<pair<int, int>>& point, const pair<int, int>& total, double& m, int idx){
    if (group_A.size() == (point.size())/2){
        pair<int, int> choose = {0, 0};
        for (pair<int, int> vec : group_A){
            choose += vec;
        }
        choose += choose;
        m = min(m, norm(total-choose));
        return;
    }
    for (unsigned i = idx; i < point.size(); i++){
        if (!check[i]){
            check[i] = true;
            group_A.push_back(point[i]);
            dfs(check, group_A, point, total, m, i);
            check[i] = false;
            group_A.pop_back();
        }
    }
}

void solve(void){
    int N; cin >> N;
    vector<pair<int, int>> point(N);
    for (int i=0; i < N; i++){
        cin >> point[i].first >> point[i].second;
    }
    pair<int, int> total = {0, 0};
    for (int i=0; i < N; i++){
        total += point[i];
    }
    double m = 1'000'000'000'000'000'000'000.0;
    vector<pair<int, int>> group_A;
    vector<bool> check(N, false);
    dfs(check, group_A, point, total, m, 0);
    cout << setprecision(15) << m << endl;
    return;
}

int main(void){
    fastio;
    int T; cin >> T;
    while (T--){
        solve();
    }
    return 0;
}