벡터 매칭

알고리즘 구분 : 수학, 브루트 포스

문제

평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다.

벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반이다.

평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

테스트 케이스의 첫째 줄에 점의 개수 N이 주어진다. N은 짝수이다. 둘째 줄부터 N개의 줄에 점의 좌표가 주어진다. N은 20보다 작거나 같은 자연수이고, 좌표는 절댓값이 100,000보다 작거나 같은 정수다. 모든 점은 서로 다르다.

출력
각 테스트 케이스마다 정답을 출력한다. 절대/상대 오차는 10-6까지 허용한다.

예제 입력 1
2
4
5 5
5 -5
-5 5
-5 -5
2
-100000 -100000
100000 100000
예제 출력 1
0.000000000000
282842.712474619038
예제 입력 2
1
10
26 -76
65 -83
78 38
92 22
-60 -42
-27 85
42 46
-86 98
92 -47
-41 38
예제 출력 2
13.341664064126334

문제 풀이

이 문제를 푸는 과정에서 벡터 매칭의 정의를 이해하는데 시간이 좀 걸렸다. 문제를 빨리 풀어야겠다는 생각이 급해서 더욱 내용이 눈에 안들어왔는지도 모르겠다.

벡터 매칭 과정에 대하여 예제를 통해서 정리하면,

이렇게 된다.

그렇기에, 모든 벡터들을 다 더한 뒤에, 사용하지 않을 벡터들을 뺀 뒤에, 벡터의 합의 길이를 계산해서 result를 min 비교를 통해 갱신해주는 과정을 거치면 된다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define ll long long
#define MAX 9223372036854775807

int t, n;
ll sumX, sumY;
double result;
vector<pair<int, int>> graph;
void dfs(ll sumX, ll sumY, int nowIdx, int cnt);
int solve();

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

    cin >> t;
    while(t--) {
        graph.clear();
        result = MAX;
        sumX = 0;
        sumY = 0;
        
        cin >> n;

        for(int i = 0; i < n; i++) {
            int a, b;
            cin >> a >> b;
            graph.push_back({a, b});
            sumX += a;
            sumY += b;
        }

        for(int i = 0; i <= n / 2; i++) {
            dfs(sumX, sumY, i, 1);
        }

        cout << fixed;
        cout.precision(15);
        cout << sqrt(result) << endl;
    }

    return 0;       
}

void dfs(ll sumX, ll sumY, int nowIdx, int cnt) {
    ll nowSumX = sumX - (2 * graph[nowIdx].first);
    ll nowSumY = sumY - (2 * graph[nowIdx].second);

    if(cnt == n / 2) {
        result = min(result, pow(nowSumX, 2) + pow(nowSumY, 2));
        
        return;
    }

    // dfs 연결
    for(int i = nowIdx + 1; i < n; i++) {
        dfs(nowSumX, nowSumY, i, cnt + 1);
    }
}

• 문제 출처 : https://www.acmicpc.net/problem/1007
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.