백준 1007번, 벡터 매칭

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

1007번: 벡터 매칭

 

요약

 

짝수 N개의 점이 속해있는 집합 P가 주어진다. 이때, 벡터 매칭은 집합 P 속의 한 점에서 다른 점을 잇는 벡터의 집합이다. 모든 점은 한 번만 사용된다.  벡터 매칭에 있는 모든 벡터의 합의 길이의 최솟값을 구한다.

---

1. 벡터의 길이는 다음과 같다. $\sqrt{( x_2 - x_1)^2 + ( y_2 - y_1)^2}$

또한, 벡터 합의 길이는 위 식에서 $x_2, y_2$ 자리에 모든 도착점 좌표들의 $x, y$값의 합을, $x_1, y_1$ 자리에 모든 시작점 좌표들의 $x, y$값의 합을 대입한 것과 같다.

 

2. 따라서, 총 N개의 점들 중 N/2개의 점들을 선택하는 모든 경우의 수에 대하여 벡터 합의 길이를 브루트포스(Brute-Force) 기법으로 구한 뒤, 그 중 최솟값을 취하여 출력하면, 문제를 해결할 수 있다.

 

3. 풀이에서 N개의 점들 중 N/2개의 점을 선택하므로 시간복잡도는 다음과 같다. O($N\times \binom{N}{\frac{N}{2}}$)

따라서, 풀이는 최대 20개의 데이터를 2초 내로 처리할 수 있다.

 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int T, N;
double x_input, y_input, xSum, ySum, xNegSum, yNegSum, ans; // 시작점들의 좌표값의 합 NegSum, 도착점들의 좌표값의 합 Sum
pair<double, double> point[20];
int Arr[20];

void BruteForce(int n, int k);

double VectorSum(double x, double y) { // x2-x1, y2-y1값이 들어왔을 때, 벡터합 반환
	return sqrt(x * x + y * y);
}

int main(void) {
	ios::sync_with_stdio(false);
	cout.tie(0);
	cout.precision(12);
	cout << fixed;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N;
		ans = -1;
		for (int j = 0; j < N; j++)
			Arr[j] = 0;
		for (int j = 0; j < N; j++) {
			cin >> x_input >> y_input;
			point[j] = { x_input,y_input };
		}
		BruteForce(0, 0);
		cout << ans << "\n";
	}
	return 0;
}

void BruteForce(int n, int k) {
	if (k == N / 2) {
		xSum = 0;
		ySum = 0;
		xNegSum = 0;
		yNegSum = 0;
		for (int i = 0; i < N; i++) {
			if (Arr[i] == 0) {
				xSum += point[i].first;
				ySum += point[i].second;
			}
			else {
				xNegSum += point[i].first;
				yNegSum += point[i].second;
			}
		}
		if (ans == -1)
			ans = VectorSum(xSum - xNegSum, ySum - yNegSum);
		else
			ans = min(ans, VectorSum(xSum - xNegSum, ySum - yNegSum));
		return;
	}
	else if (n == N)
		return;
	else {
		for (int i = 0; i < 2; i++) {
			if (i == 0)
				BruteForce(n + 1, k);
			else {
				Arr[n] = 1;
				BruteForce(n + 1, k + 1);
				Arr[n] = 0;
			}
		}
	}
}

[raararaara 님의 피드백]

1) 실수연산에 관하여
실수 연산에는 오차가 발생할 가능성이 있기 때문에 최대한 정수형으로 연산을 진행한 뒤, 정답을 실수형으로 출력

2) 시간복잡도에 관하여
최종 시간복잡도는 O($N\times \binom{N}{\frac{N}{2}}$)이다. (반영)