[백준알고리즘] 1007번: 벡터 매칭 -C++

[백준알고리즘] 1007번: 벡터 매칭 -C++

1007번: 벡터 매칭 (acmicpc.net)

1007번: 벡터 매칭

문제를 이해하는데 어려움이 있었다. 

 

정확히 무엇이 P이고 벡터 매칭은 무엇이며 벡터의 집합에 대한 설명, V에 대한 설명 등등 처음 봤을 때 이해하기 어려운 내용들이었다. 결국 이 부분들은 다른 질문 게시판의 글이나 다른 블로그의 글을 통해 이해하고 문제를 풀었다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

 

문제 이해

먼저, 문제를 이해한 내용에 대해 문제를 풀어서 설명하겠다.

 

• 평면 상에 N개의 점이 있다.
• 이 N개의 점의 집합이 P이다.
• P의 벡터 매칭을 V라고 하며 벡터의 집합을 의미한다.
• P의 벡터 매칭은 점의 집합 P에서 각 점을 한 번씩만 사용해셔 한 점에서 다른 한 점으로 가는 벡터의 집합인 것이다.
• 따라서 하나의 벡터를 만드는 데 두 개의 서로 다른 점을 사용하게 되어서 V의 길이는 P의 길이의 절반이다. (N/2)
• P의 벡터 매칭 V는 여러 경우가 존재할 수 있는데, V에 있는 벡터의 합의 길이(스칼라)가 최소가 되는 경우의 벡터의 합을 구하면 된다.

 

벡터 연산

이제 각각 벡터를 구하는 방법과 벡터의 합을 구하는 방법을 알면 된다.

 

점으로부터 벡터 구하기

먼저, 벡터를 구하는 방법에 대해서 살펴보겠다.

 

점 A(1, 0)과 점 B(0, 1)이 있다고 했을 때, 두 개의 벡터를 생각할 수 있다. 하나는 A→B, 다른 하나는 B→A이다.

각각의 벡터는 다음과 같다.

• A→B: B - A = (0, 1) - (1, 0) = (-1, 1)
• B→A: A - B = (1, 0) - (0, 1) = (1, -1)

즉, 일반화해서 본다면 A\((x_1, y_1)\)과 B\((x_2, y_2)\)라는 두 점이 있을 때 벡터는 다음과 같이 두 개 존재하게 된다.

• A→B: B - A = \((x_2, y_2) - (x_1, y_1) = (x_2-x_1, y_2-y_1)\)
• B→A: A - B = \((x_1, y_1) - (x_2, y_2) = (x_1-x_2, y_1-y_2)\)

 

벡터의 합과 벡터의 합의 길이 구하기

위의 과정을 통해 구한 벡터를 통해 벡터의 합과 벡터의 합의 길이(스칼라)를 구하는 방법을 살펴보겠다.

 

A→B와 C→D라는 벡터가 각각 \((X_1, Y_1)\), \((X_2, Y_2)\) 일 때 A→B라는 벡터와 C→D라는 벡터의 합은 다음과 같이 두 벡터를 말 그대로 합해주면 된다.

A→B + C→D: \((X_1, Y_1) + (X_2, Y_2) = (X_1+ X_2, Y_1+Y_2)\)

 

여기서, 이제 이 벡터의 합을 구해야 하는데, 벡터의 합도 벡터이기 때문에 간단히 벡터로 예시를 들면 다음과 같다.

\(v = (x, y)\)

\(|v| = \sqrt{x^2+y^2}\)

---

 

이렇게까지 알았다면 문제를 풀기 쉬워진다.

 

특히, 벡터의 합을 구하는 점과 각 점을 한 번씩만 사용해서 벡터들을 만든다는 점 때문에 쉬워지게 된다.

첫 번째 예제와 같은 경우에는 각 점을 A, B, C, D라고 했을 때, 이 안에서 나올 수 있는 벡터는 다음과 같다.

• A→B, C→D = (B-A), (D-C)
• A→C, B→D = (C-A), (D-B)
• B→C, A→D = (C-B), (D-A)
• ...

이러한 벡터들의 집합인 V안에서 벡터의 합들을 구하게 되면 다음과 같다.

• (B-A), (D-C) = B - A + D - C = - A + B + D - C
• (C-A), (D-B) = C - A + D - B = - A - B + C + D
• (C-B), (D-A) = C - B + D - A = - A - B + C + D
• ...

즉, 기존 점들의 합과 차로 벡터들의 합을 구할 수 있게 되는 것이다.

 

게다가 점들의 절반은 시작점이고 나머지 절반은 끝나는 점이기 때문에 절반은 더해주고 절반은 빼주면 된다.

 

그렇게 구한 최종 값을 스칼라로 구해주면 된다.

---

 

아래는 통과한 C++ 코드다.

이런 방식으로 대부분 푼 것 같다. 배열로 푸신 분들의 코드가 더 깔끔한 것 같다. 그리고 계속해서 레퍼런스 인자를 넘겨주기 때문에 코드 자체는 안 이쁜 것 같긴 하다. 클래스를 쓴다면 더 깔끔하게 짤 수는 있을 것 같다.

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

void solve(void);

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

	int test_case;
	std::cin >> test_case;
	for (int t = 0; t < test_case; t++)
		solve();
}

double get_minimum(const int idx, const int count, std::pair<int, int> current, std::vector<std::pair<int, int>>& points)
{
	if (points.size() == idx)
	{
		if (count == points.size() / 2)
			return sqrt(pow(current.first, 2) + pow(current.second, 2));
		return LLONG_MAX;
	}

	std::pair<int, int>& temp = points[idx];
	
	if (points.size() / 2 == count)
		return get_minimum(idx + 1, count, std::make_pair(current.first - temp.first, current.second - temp.second), points);
	
	double return_a = get_minimum(idx + 1, count, std::make_pair(current.first - temp.first, current.second - temp.second), points);
	double return_b = get_minimum(idx + 1, count + 1, std::make_pair(current.first + temp.first, current.second + temp.second), points);

	return return_a < return_b ? return_a : return_b;
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::vector<std::pair<int, int>> point;
	for (int i = 0; i < n; i++)
	{
		int x, y;
		std::cin >> x >> y;
		point.push_back(std::make_pair(x, y));
	}

	double minimum = LLONG_MAX;
	double m = get_minimum(0, 0, std::make_pair(0, 0), point);
	minimum = m < minimum ? m : minimum;

	std::cout << std::fixed;
	std::cout.precision(12);
	std::cout << minimum << '\n';
}