[백준 알고리즘] 1007번 벡터 매칭 c++

벡터는 방향성이 존재하므로 +,- 둘 다 가능한 것을 놓치면 안 된다.

처음에 벡터의 마이너스 경우는 생각하지 않았다가 헤맸다ㅜㅜ

 

벡터의 합은 V1<x1, y1> + V2<x2, y2> = V<x1+x2, y1+y2>이고,

점 N개에 대해서 벡터의 개수는 N/2이므로,

시작점 N/2개와 끝점 N/2개를 갖는다.

따라서 N개중에서 N/2개를 뽑는 조합을 DFS로 구현하고,

벡터의 합이 Va<sum_x, sum_y>과 Vb<total_x-sum_x, total_y-sum_y>일 때

Va가 시작점이고 Vb가 끝점일 때의 벡터의 길이와

Va가 끝점이고 Vb가 끝점일 때의 벡터의 길이 중에서

최솟값을 구해서 출력한다.

 

*벡터의 길이는 sqrt(x*x +y*y)

*소수점은 double형, 출력시 printf로도 가능하고 c++에서 precision도 사용 가능하다.

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

using namespace std;
using ll = long long;

int n, x[20],y[20];
ll total_x, total_y;
ll res;

void DFS(int l, int pos, ll sum_x, ll sum_y){
	if(l == n/2){
		res = min(res, (2*sum_x - total_x)*(2*sum_x - total_x) + (2*sum_y - total_y)*(2*sum_y - total_y));
		res = min(res, (total_x - 2*sum_x)*(total_x - 2*sum_x) + (total_y- 2*sum_y)*(total_y - 2*sum_y));
	}
	else{
		for(int i=pos; i<n; i++){
			DFS(l+1, i+1, sum_x + x[i], sum_y + y[i]);
		}
	}
}
int main(){
	int t;
	cin >> t;

	while(t--){
		cin >> n;

		total_x = 0;
		total_y = 0;
		res = LLONG_MAX;

		for(int i=0; i<n; i++){
			cin >> x[i] >> y[i];
			total_x += x[i];
			total_y += y[i];
		}

		DFS(0,0,0,0);

		double r = sqrt(res);

		printf("%.12lf\n",r);
	}

	return 0;
}