[C++ 백준 풀이][Gold II] 1007번 : 벡터 매칭 (재귀함수 + 벡터 연산 기법)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 문제 '1007번 : 벡터 매칭'에 대한 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Gold II이며, 재귀함수 응용과 벡터 연산 기법을 개념으로 다룰 것입니다.

 

 

1007번 : 벡터 매칭

 

짝수 개의 점들의 좌표가 주어질 때, 이들의 적절한 조합으로 벡터들을 만들었을 때 이 벡터들의 합이 최소가 되는 벡터 합의 값을 구하는 문제입니다.

예를 들어 (5, 5)와 (5, -5)가 있으면 각 점을 시작점으로 잡냐 끝점으로 잡냐에 따라 만들 수 있는 벡터는 (0, 10)과 (0, -10)이 있습니다.

점들의 수가 많아지면 선택할 수 있는 조합의 수가 많아지므로 이들을 모두 고려해봐야 하는 문제입니다.

계산을 하지 않고는 단순히 벡터 합의 최솟값을 알 수 없으므로 브루트포스 알고리즘에 가깝게 구현해야 할 것으로 보입니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래 접은 글에 정리되어 있으니 참고해주세요.

#include <iostream>
#include <cmath>
#define INF 1000000000
using namespace std;

int T, N;
double vec[21][2], selected[21] = {0, }, sum_x, sum_y, temp_x, temp_y, sum, Min;
double Abs(double a) { return a>=0?a:-a; }

void calc_sum() {
    for(int i=0; i<N; i++)
        if(!selected[i]) {
            sum_x -= 2*vec[i][0];
            sum_y -= 2*vec[i][1];
        }
    sum = sqrt(sum_x*sum_x + sum_y*sum_y);
    if(Abs(sum) < Min) Min = Abs(sum);
}

void selection(int cnt, int recent) {
    if(cnt <= 0) {
        temp_x = sum_x;
        temp_y = sum_y;
        calc_sum();
        sum_x = temp_x;
        sum_y = temp_y;
        return;
    }
    for(int i=recent; i<N; i++) {
        if(!selected[i]) {
            selected[i] = 1;
            selection(cnt-1, i+1);
            selected[i] = 0;
        }
    }
}


int main() {
    cin >> T;
    for(int i=0; i<T; i++) {
        Min = INF, sum_x = sum_y = 0;
        cin >> N;
        for(int j=0; j<N; j++) {
            cin >> vec[j][0] >> vec[j][1];
            sum_x += vec[j][0];
            sum_y += vec[j][1];
        }
        selection(N/2, 0);
        printf("%.7lf\n", Min);
    }
}

 

이 문제의 가장 큰 핵심은 모든 경우의 수를 검사하는 것은 고사하고 벡터 연산을 최소 연산으로 구하는 기법입니다.

(a, b)와 (c, d)로 벡터 연산을 하면 (a-c, b-d) 또는 (c-a, d-b) 두 가지의 경우가 있습니다.

이것을 빨리 연산하기 위한 방법으로 (a+c, b+d)를 기본 form으로 잡아두고 여기에 (-2a, -2c) 또는 (-2b, -2d) 연산만 해주는 것입니다.

위의 main 함수의 sum_x와 sum_y 값이 이 기본 form에 해당하고, calc_sum에서 수행하는 연산이 이에 해당합니다.

 

N개의 점이 주어지면 sum을 구한 뒤 이 중에 N/2개의 점들을 2배로 빼주면 되는 것이므로, selection 함수에서는 N/2개의 점을 선택하는 기능을 구현하였습니다.

재귀적으로 일부를 선택하는 구현은 이전에도 많이 다루었으니 이전 포스트들을 참고하면 좋고, 아니면 코드만 참고하셔도 충분히 이해 가능할 것입니다.

 

 

풀이 코드를 제출해보면 184ms라는 짧지 않은 시간에 문제가 해결됨을 알 수 있습니다.

문제에서 N은 최대 20으로 주어졌으므로 재귀함수로 선택 부분을 구현해도 시간 부족이 크게 없었던 문제였습니다.