happy318
팽도리블로그
happy318
전체 방문자
오늘
어제
  • 전체글 (252)
    • 공부 (5)
      • Algorithm 정리 (0)
      • 논문리뷰 (1)
      • C++ (2)
      • Python (2)
      • Java (0)
      • Back-end (0)
      • Front-end (0)
      • Embedded (0)
    • 코딩테스트 (218)
      • Python 문제풀이 (100)
      • C++ 문제풀이 (108)
      • Python template (9)
      • C++ template (1)
    • 일상 (20)
      • 맛집 (13)
      • 쇼핑 (5)
      • 아무 일상 (2)
    • 게임 (9)
      • 메이플스토리 (9)

최근 글

인기 글

hELLO · Designed By 정상우.
happy318

팽도리블로그

코딩테스트/C++ 문제풀이

[백준] 벡터 매칭

2023. 2. 6. 00:31

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

 

1007번: 벡터 매칭

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

www.acmicpc.net

우선 문제부터 간단하게 요약하면,

 

점들이 N(짝수) 개 찍혀 있고, 이 점들을 둘씩 이으면 벡터가 생기게 됩니다. 이런 벡터들의 합의 최솟값을 구하는 문제입니다.

 

<Solution>

어렵게 생각하지 말고, 벡터의 합은 각각의 성분들을 더하면 되는 것을 생각해봅시다. 

 

만약 <1,2> <3,4> 이렇게 두개의 벡터가 있다면, 벡터의 합은 <4,6>이 되고 이 길이가 우리가 구하는 벡터의 합의 길이입니다. 한마디로, N개의 점들중 시작점 N/2개를 뽑아 벡터를 구성한뒤, 벡터의 합을 구하고 그중 최솟값을 구하면 됩니다.

 

N개의 점들중 N/2개의 점을 뽑는 것은 조합입니다. 조합은 일반적으로 python과 같은 언어에는 내장되어 있지만, c++의 경우 dfs로 구현합니다. 이렇게 단순한 조합은 binary tree를 이용한 조합으로 구현하는 것이 간편하고 이렇게 구현한 조합에 각각의 경우에 대해 길이를 구할 수 있도록 하면 됩니다.

 

가지치기는 만약 남은 것들을 모두 뽑아도, N/2 개를 뽑지 못하는 경우에 대해 진행하면 됩니다.

 

실제 구현은 아래와 같습니다.

 

#include <iostream>
#include <cmath>
#include <climits>

using namespace std;

int T; int N;

struct dot{
    int x;
    int y;
};

dot dots[25];
int index_array[25];

double ans;

double calculate_dist(){
    int left_sum_x = 0;
    int left_sum_y = 0;
    int right_sum_x = 0;
    int right_sum_y = 0;
    for(int i = 0; i<N; i++){
        if(index_array[i]){
            left_sum_x += dots[i].x;
            left_sum_y += dots[i].y;
        }
        else{
            right_sum_x += dots[i].x;
            right_sum_y += dots[i].y;
        }
    }
    return sqrt(pow(left_sum_x - right_sum_x,2) + pow(left_sum_y - right_sum_y, 2));
}


// combination using binary tree
void dfs(int step, int how_many_seleted){
    // when will it return 
    if(step == N || how_many_seleted == N/2){
        if(!(how_many_seleted == N/2)) return;
        ans = min(ans, calculate_dist());
        return;
    }

    // 발전 포기 (다음 모든걸 골라도 N/2개 못고를 때)
    if(how_many_seleted + (N - step) < N/2){
        return;
    }

    // 현재 step 고르는 경우
    index_array[step] = 1;
    dfs(step+1, how_many_seleted+1);
    index_array[step] = 0;

    // 현재 step 고르지 않는 경우
    dfs(step+1, how_many_seleted);
    
    return;
}


int main(){
    cin >> T;

    for(int i = 0; i<T; i++){
        // solve for each testcase
        cin >> N;

        // get input
        for(int j = 0; j<N; j++){
            cin >> dots[j].x >> dots[j].y;
        }

        // solve by using dfs
        ans = numeric_limits<double>::max();
        dfs(0, 0);
        cout << fixed;
        cout.precision(12);
        cout << ans << endl;
    }
}
반응형

'코딩테스트 > C++ 문제풀이' 카테고리의 다른 글

[백준] 다각형의 면적  (0) 2023.02.13
[백준] 최소 스패닝 트리  (0) 2023.02.12
[백준] 알파벳  (0) 2023.02.05
[백준] 녹색 옷 입은 애가 젤다지?  (0) 2023.02.05
[백준] 알고스팟  (0) 2023.02.05
    '코딩테스트/C++ 문제풀이' 카테고리의 다른 글
    • [백준] 다각형의 면적
    • [백준] 최소 스패닝 트리
    • [백준] 알파벳
    • [백준] 녹색 옷 입은 애가 젤다지?
    happy318
    happy318

    티스토리툴바