백준 1007 벡터 매칭

백준 1007 ←클릭
벡터 매칭 문제이다. 조합을 사용하여 문제를 해결하면 brute-force 알고리즘에 비해 시간 복잡도를 상당히 줄일 수 있다.

변수 설정

P: 점들을 저장하는 벡터
minimum : 최소값을 저장
b: bool값을 저장하는 벡터. 조합 구현시 사용
sel: $nCr$에서 $r$에 해당하는 값. (N/2)
sel_first:선택된 점들의 x값들의 합
sel_second:선택된 점들의 y값들의 합
usel_first:나머지 점들의 x값들의 합
usel_second:나머지 점들의 y값들의 합

조합(combination)구현

문제를 해결하기 위해 조합을 구현해야 하는데 방법을 몰라 구글링을 했다. $nCr$을 구현하는 방법은 다음과 같다.

• 길이가 n인 벡터에 true값을 r개 push_back하고 false를 n-r개 push_back한다.
• algorithm헤더의 next_permutation함수를 이용하여 벡터의 순서를 바꾼다.
• 벡터의 값이 true인 인덱스에 해당하는 값을 원래 벡터에서 선택한다.

이 방법을 사용하면 순열을 사용하여 조합을 구현할 수 있다. 이 방법을 보면 직관적으로 왜 조합이 구현되는지 알 수 있을 것이다.

아이디어

• 전체의 점 중 N/2개의 점을 선택하여 x값과 y값을 모두 더하여 벡터를 만들고, 나머지 점도 값은 방법으로 벡터를 만든다.
• 두 벡터를 빼서 벡터의 길이를 구한다.
• 모든 조합에 대해 벡터의 길이를 구하고 최소 값을 출력한다.

예시로 점이 20개인 케이스로 설명하면 임의로 점을 2개씩 만든 벡터를 V1~V10까지 있다고 하자. 이 케이스의 벡터$V$는 $\sum_{i=1}^{10} V_i$일 것이다. $V_i$가 $P_{i1}$ $P_{i2}$로 이루어져 있다고 가정하면 $V_i$ = $P_{i2}$ $-$ $P_{i1}$ 일 것이고 이를 위 식에 대입하면 $\vert X \vert$ = $\sum_{i=1}^{10} P_{i2}$ - $\sum_{i=1}^{10} P_{i1}$ 이 뜻이 20개의 점에서 임의로 10개를 선택하여 x값과 y값을 모두 합치고 나머지 10개의 값과 각각 뺄셈 연산을 진행하여 $V$를 구할 수 있다.
우리는 벡터의 크기 $\vert V \vert$를 구해야 하기 때문에 $\sqrt{(V.x)^2 + (V.y)^2}$값을 구하고 모든 조합에 대해 $\vert V \vert$값을 구한 뒤 최소값을 출력하면 된다.

코드

github

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
double cal_vec(pair<int, int> f);
int main() {
	cout << fixed;
	cout.precision(6); //문제 조건에 의거 소수점 6째까지 출력
	//freopen("input/1007_input.txt", "r", stdin);
	int T, N;
	
	cin >> T;
	for (int i = 0; i < T; i++) {
		vector<pair<int, int>> P;
		pair<int, int> p[20];
		double minimum = 987654321;
		cin >> N;
		for (int j = 0; j < N; j++) {
			cin >> p[j].first >> p[j].second;
			P.push_back(p[j]);
		}
		sort(P.begin(), P.end());
		int sel = N / 2;
		vector<bool> b(sel, false);
		b.insert(b.end(), sel, true);
		do {
			int sel_first = 0;
			int sel_second = 0;
			int usel_first = 0;
			int usel_second = 0;
			for (int j = 0; j < N; j++) {
				if (b[j]) {//selected 와 !selected계산
					sel_first += P[j].first;
					sel_second += P[j].second;
				}
				else {
					usel_first += P[j].first;
					usel_second += P[j].second;
				}
			}
			minimum = min(minimum, cal_vec(make_pair(usel_first - sel_first, usel_second - sel_second)));
		} while (next_permutation(b.begin(), b.end()));
		cout << minimum << endl;
	}
	
	
	return 0;
}

double cal_vec(pair<int, int> f) {
	//cout << "cal_vec: " << f.first << "," << f.second << endl;
	return pow(pow((f.first), 2) + pow((f.second), 2), 0.5);
}

느낀점

처음 별 생각없이 단순하게 brute-force로 구현하였다가 시간초과를 받았다. 시간 복잡도를 계산해보니 $O(n) = n!$였다. 시간 복잡도를 개선하기 위해 생각을 해보니 위와 같이 구현하면 시간 복잡도가 $O(n) = n^2$정도로 줄기 때문에 위와 같이 구현을 했는데 앞으로는 생각없이 코딩하는 습관을 버리고 미리 시간복잡도를 계산해서 구현을 해야겠다..
brute-force 구현

정답~.~