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

문제

• 1007번 : 벡터 매칭
• Rank : Gold II
• 링크 : https://www.acmicpc.net/problem/1007

1007번: 벡터 매칭

 

풀이 전략

• 평면상의 점들을 두개씩 짝지어 벡터를 만들고, 그 벡터들의 합을 구한 후 길이로 변환한다.
• 다만, 브루트포스로 for문을 돌릴 경우 N! 만큼의 계산이 필요하여 시간제한에 맞출 수 없다.
• V1 + V2 + V3 + V4 + .... = (a1-b1) + (a2 - b2) + ... = (a1 + b1 - b1 - b1).... 이므로
  • 벡터들의 합 = (전체 좌표의 합) - 2 * (점 절반의 합)이 된다.
• 해당 방법을 사용하여, N개의 점 중 N/2개의 점을 도출해낸 뒤, 벡터 길이의 최소값을 구하는 방법으로 풀이한다.
  • for문 대신 재귀함수를 사용하여 현재 인덱스 / 선택해야 하는 점의 개수를 인자로 사용하는 방식으로 구현하였다. N의 최대값이 20이었으니 비트마스킹을 사용해도 괜찮았을 듯.

	void pick(int left, int currentIdx, long long vectorX, long long vectorY)
	{
		if (left == 0)
		{
			long long X = totalX - vectorX - vectorX;
			long long Y = totalY - vectorY - vectorY;
			unsigned long long temp = (X * X) + (Y * Y);
			if (temp < MinValue)
			{
				MinValue = temp;
			}
			return;
		}
		if (currentIdx >= N)
			return;
		pick(left, currentIdx + 1, vectorX, vectorY);
		pick(left - 1, currentIdx + 1, vectorX + pos[currentIdx][0], vectorY + pos[currentIdx][1]);
	}

 

전체 소스 코드

//Backjoon Problem No.1007
//https://www.acmicpc.net/problem/1007
//Mist16, 2022-01-24
#include <iostream>
#include <limits>
#include <math.h>

using namespace std;

class VectorMatching
{
private:
	int N;
	int pos[20][2];
	long long totalX;
	long long totalY;
	unsigned long long MinValue;
public:
	VectorMatching()
	{
		N = 0;
		MinValue = 0xffffffffffffffff;
		totalX = 0;
		totalY = 0;
	}

	void input()
	{
		cin >> N;
		for (int i = 0; i < N; i++)
		{
			cin >> pos[i][0] >> pos[i][1];
			totalX += pos[i][0];
			totalY += pos[i][1];
		}
	}

	void Run()
	{
		pick(N / 2, 0, 0, 0);
		long double temp = sqrtl(MinValue);
		cout.precision(16);
		cout << temp << endl;
	}

	void pick(int left, int currentIdx, long long vectorX, long long vectorY)
	{
		if (left == 0)
		{
			long long X = totalX - vectorX - vectorX;
			long long Y = totalY - vectorY - vectorY;
			unsigned long long temp = (X * X) + (Y * Y);
			if (temp < MinValue)
			{
				MinValue = temp;
			}
			return;
		}
		if (currentIdx >= N)
			return;
		pick(left, currentIdx + 1, vectorX, vectorY);
		pick(left - 1, currentIdx + 1, vectorX + pos[currentIdx][0], vectorY + pos[currentIdx][1]);
	}

};

int main()
{
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int testCases;

	//input n, pipemap;
	cin >> testCases;
	for (int i = 0; i < testCases; i++)
	{
		VectorMatching vMatch;
		vMatch.input();
		vMatch.Run();
	}
	return 0;
}

여담

• 수학적으로 계산을 정리함으로서 계산 단계를 줄일 수 있는 문제였다. 바로 코딩하기보다는, 식을 확인하고 한 번 정리한 뒤 풀이에 들어가는 것이 좋을 듯 하다.
• n개의 수 중 m개를 선택하는 상황에서, for문으로 n회를 돌리는 대신, i번째 수를 넣을지/안 넣을지로 재귀 함수를 사용하는 방법도 괜찮은 것 같다.