[BOJ] 백준 1007 - 벡터 매칭 C++ 풀이

풀이과정

1. 두 점 (x1, y1), (x2,y2) 에 대하여 벡터는 (x1-x2, y1-y2) 또는 (x2-x1, y2-y1)을 만들 수 있다.
2. 1번과 같은 방식으로 네 점에 대하여 생성가능한 합벡터는 (+x1-x2-x3+x4, +y1-y2-y3+y4), (+x1-x2+x3-x4, +y1-y2+y3-y4), (+x1+x2-x3-x4, +y1+y2-y3-y4)과 이 세가지 벡터에 -를 붙인 벡터이다. → 6가지 
   • 몇가지 경우를 하다 보면 +와 -의 조합 문제임을 알 수 있다.
3. 즉, 서로 다른 N(짝수)개의 점에 대하여 생성 가능한 벡터를 nC(n/2)의 조합으로 선택하여 +를 붙이고, 나머지 n/2개의 벡터에 -를 붙여 더하면 생성 가능한 합벡터를 전부 확인 가능하다
   • 예를 들어 N=4 일때 4C2 : 0011, 0101, 0110, 1001, 1010, 1100 (1은 선택, 0은 미선택) 을 comb(vector)로 두고 points의 해당 인덱스가 1일때는 +, 0이면 -를 곱하여 더한다.
4. 모든 조합에 대하여 완전탐색해가며 최소값을 찾는다. 

 

 

코드

 

•  c++에서 조합을 사용하는 방법으로 next_permutation을 사용한다.
  • 사용 전 sorting 필수
  • 아래 코드에서는 0과 1뿐이기 때문에 첫번째 for문에서 세팅하는 것으로 sorting 대체
• cout시 소수점 n자리 수까지 출력하는 것은 cout.precision(n)을 사용하여 설정한다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

int main() {
	int T; //# of test case
	cin >> T;
    
    //소수점 7자리까지만 출력
	cout << fixed;
	cout.precision(7);
    
	while (T--) {
		int N, //# of points
			sum_x = 0, sum_y = 0; //sum of vector -> x, y

		vector<pair<int, int>> points;
		vector<int> comb;

		long long min = -1, now;

		cin >> N;
		points.resize(N);
		comb.resize(N, 0);

		for (int i = 0; i < N; i++) {
			cin >> points[i].first >> points[i].second;
			if (i >= N / 2) comb[i] = 1; //instead sorting comb
		}

		//brute force(완전탐색)
		do {
			sum_x = sum_y = 0;
			for (int i = 0; i < N; i++) {
				if (comb[i]) {
					sum_x += points[i].first;
					sum_y += points[i].second;
				}
				else {
					sum_x -= points[i].first;
					sum_y -= points[i].second;
				}
			}
            
			now = pow(sum_x, 2) + pow(sum_y, 2);
			if (min == -1 || min > now) min = now;

		} while (next_permutation(comb.begin(), comb.end()));
		
        //# of plus == # of minus --> min of vector size

		cout << sqrt(min) << endl;
		points.clear();
	}
}

 

 

고찰

• 처음엔 pow함수를 쓰지 않고 sum_x*sum_x 와 같은 방법으로 구하고자 하였는데 이상하게 연산이 제대로 수행되지 않았다. 
• 길이의 최솟값을 구하는 문제이기 때문에 ++--와 --++ 중 한가지만 수행해도 되는데, 어떻게 선택할지 잘 모르겠다.