1007번: 벡터 매칭 - 수학, 브루트포스

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

1007번: 벡터 매칭

 

두 점 (x1, y1), (x2, y2)가 있다고 할 때, 벡터는 (x1, y1) - (x2, y2)이다.

점이 N개 있을 때 벡터의 합은, 벡터를 N/2개 더하면 되므로 ((xa, ya) - (xb, yb)) + ((xc, yc) - (xd, yd)) + ... 이다.

이는 {(xa, ya) + (xc, yc) + ... } - {(xb, yb) + (xd, yd) ...} 이다.

즉 첫 번째 중괄호에 들어갈 점 N/2개만 고르고 나머지 N/2개의 점을 빼면 답이다. nC(n/2) 내로 답이 나올 수 있다.

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <string>
#include <iomanip>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

vector<pii> v;
bool vis[20];
int N;
double mn;

void f(int idx, int cnt)
{
	if (cnt == N / 2)
	{
		int x{ 0 }, y{ 0 };
		for (int i{ 0 }; i < N; i++)
		{
			auto [a, b] = v[i];
			if (vis[i])
			{
				x += a; y += b;
			}
			else
			{
				x -= a; y -= b;
			}
		}
		mn = min(mn, sqrt(pow(x, 2) + pow(y, 2)));
		return;
	}


	for (int i{ idx }; i < N; i++)
	{
		if (!vis[i])
		{
			vis[i] = true;
			f(i + 1, cnt + 1);
			vis[i] = false;
		}
	}
}

void solve()
{
	v.clear();
	mn = 1e9;

	cin >> N;
	for (int i{ 1 }; i <= N; i++)
	{
		int x, y; cin >> x >> y;
		v.push_back({ x, y });
	}

	f(0, 0);
	cout << fixed << setprecision(13) << mn << "\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int T; cin >> T;
	for (int i{ 1 }; i <= T; i++) solve();
}

머리로 생각하지 말고 해당 수식을 직접 써가며 풀었어야 했다. dp로 오해하기 딱 좋은 문제.