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

1007번: 벡터 매칭

브루트 포스

---

1. 문제해결 아이디어

처음에 단순히 최대 20개의 점 중에서 2개씩 묶어 나가는 방법으로 풀려고 했다.

위 방법대로 하면 O(20 * 18 * ... * 4 * 2) 같은 끔찍한 시간복잡도가 나와 불가능함을 알 수 있었다.

 

v1<3, 5>, v2<-2, 3> 이라는 벡터가 있다고 가정해보자

v1 + v2 = <(3+(-2)), (5+3)> = <1, 8> 이 된다.

여기서 알 수 있는점은 N개의 점 중에서,

N/2개의 점은 시작점이 될 것이고, 나머지 N/2개의 점은 도착점이 되는 것을 알 수 있다.

따라서 시작점 10개만 선택한다면 O( 20C10 )의 시간복잡도를 가지고 벡터의 총 합을 구할 수 있다. 

---

2. 코드

<+14> ~ <+30> vec_sum() : 지금까지 선택한 N/2개의 시작점과 나머지 도착점을 가지고 벡터의 총 합을 구하는 함수

<+32> ~ <+52> dfs(int now, int cnt) : dfs를 통해 완전탐색을 하면서 방문한 벡터의 수가 N/2개가 되면 벡터의 총 합을 구하고 최솟값을 갱신해준뒤에 return하는 함수

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#define pii pair<int, int>
 
using namespace std;
 
int N;
vector<pii> points;
double result;
bool visited[21];
 
double vec_sum(){
    pii vec = {0, 0};
    for(int i = 0; i < N; i++){
        // 시작점인 경우
        if(visited[i]){
            vec.first -= points[i].first;
            vec.second -= points[i].second;
        }
        // 도착점인 경우
        else{
            vec.first += points[i].first;
            vec.second += points[i].second;
        }
    }
    
    return sqrt(pow(vec.first, 2) + pow(vec.second, 2));
}
 
void dfs(int now, int cnt){
    if(cnt == N/2){
        result = min(result, vec_sum());
        return;
    } 
    
    for(int i = now; i < N; i++){
        visited[i] = true;
        dfs(i+1, cnt+1);
        visited[i] = false;
    }
}
 
void input(){
    int a, b;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> a >> b;
        points.push_back({a, b});
    }
}
 
int main(){
    int test;
    cin >> test;
    while(test--){
        memset(visited, 0, sizeof(visited));
        points.clear();
        result = 1e9+7;
    
        input();
        
        dfs(0, 0);
        printf("%.7lf\n", result);
    }
    
    return 0;
}
 

좌표의 완전 탐색