[Algorithm]Baekjoon 1007번 :: 벡터 매칭

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
struct Node
{
    double y;
    double x;
};
 
int t, n;
bool visited[21] = { false };
vector<Node> nodes(21);
int nSize = 0;
int targetSize = 0;
double answer = 0;
 
 
double CalcMinValue()
{
    Node node = { 0, 0 };
 
    for (int i = 0; i < n; ++i)
    {
        if (visited[i]) // 더할것
        {
            node.y -= nodes[i].y;
            node.x -= nodes[i].x;
        }
        else
        {
            node.y += nodes[i].y;
            node.x += nodes[i].x;
        }
    }
 
    return sqrt(pow(node.y, 2) + pow(node.x, 2));
}
 
void DFS(int index)
{
    if (nSize == targetSize)
    {
        answer = min(answer, CalcMinValue());
 
        return;
    }
 
    for (int i = index + 1; i < n; ++i)
    {
        visited[i] = true;
        ++nSize;
 
        DFS(i);
 
        --nSize;
        visited[i] = false;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    while (t--)
    {
        cin >> n;
        
        targetSize = n / 2;
        nSize = 0;
        answer = 100000000;
 
        for (int i = 0; i < n; ++i)
        {
            cin >> nodes[i].y >> nodes[i].x;
        }
 
        // N개의 점중에서 N/2개의 점을 순서없이 뽑기
        DFS(-1);
 
        printf("%f\n", answer);
    }
}
 
 

 

 

최대 20개의 점으로 최대 10개의 벡터를 만든 후, 이 벡터의 합의 최소값을 구하는 문제이다.

그냥 단순하게 완전탐색한다 치면은 경우의 수가 너무 많다.

20개의 점들 중에서 무작위로 2개의 점씩 묶은 다음, 벡터를 만들어야하는데 점 A,B 가 있을 때 벡터가 1개가 생기는 게 아니라 2개가 생긴다.

A->B 벡터랑 B->A 벡터.

 

그래서 단순하게 완전탐색하려하면 시간초과에 걸린다.

그래서 모든 벡터의 합을 빠르게 구하는 방법을 알아야 한다.

 

점 A1,A2,A3, B1,B2,B3가 있다고 가정한다.

그리고 여기서 벡터 3개를 만든다.

각각 (B1 - A1), (B2 - A2), (B3 - A3) 라는 벡터 3개를 만들었다.

이 3개의 벡터의 합은 결국 (B1 + B2 + B3) - (A1 + A2 + A3) 이다. 벡터의 합은 그냥 벡터를 전부 더한거니까.

 

여기서 B1이든 B2든 A1이든, 그냥 최대 20개의 점들 중 하나일 뿐이다.

 

즉, 주어지는 점들의 절반을 조합으로 구하고 전부 더한다음 (위의 B1,B2,B3), 나머지점들(위의 A1,A2,A3) 을 전부 빼주면 모든 벡터의 합이 된다.

20개의 점들 중에서 중복없이 점 10개를 뽑아야하니 20C10이고, 이 값은 184756 이라고 하니 충분히 시간안에 해결할 수 있다.