[ SWEA / 1494 ] 사랑의 카운슬러 (C++)

SW Expert Academy

 

난이도 : D4 
알고리즘 유형 : 조합, 완전탐색 
풀이 시간 : 38분 

문제 풀이 

임의의 지렁이 두 마리를 매칭시킨 후 한 지렁이(A)가 다른 지렁이(B)가 있는 곳으로 가도록 할 때, 모든 지렁이들이 움직인 벡터 합의 최소값을 구하자. 

벡터 합의 크기는 다음과 같다. $|V| = |(x, y)| = x * x + y * y$

 

이 문제를 해결하기 위해서는 먼저 벡터의 개념을 알아야 한다.

a벡터와 b벡터를 각각 지렁이의 위치라고 할 때, c벡터는 a지렁이가 b지렁이까지 이동한 거리가 된다. 여기서, 벡터의 합 공식으로 $\vec{b} = \vec{a} + \vec{c}$가 성립하기 때문에 움직인 크기 c 를 구하기 위해서는 $\vec{c} = \vec{b} - \vec{a}$를 진행해주면 된다. 

또한, 벡터는 교환법칙과 결합법칙이 성립하기 때문에 하나의 지렁이를 선택할 때 위치를 일일이 구해주지 않고 한번에 구해주어도 무방하다.

 

문제에서 모든 지렁이는 자신의 짝을 찾게 되어있기 때문에 이동해야 할 지렁이 $n / 2$마리만 선택한 다음, 이동해야 하는 지렁이의 위치는 빼주고, 기다리는 지렁이의 위치는 더해준 다음 벡터의 크기를 구해주면 된다.

 

문제에서 주의해야 할 사항은 바로 변수의 범위이다. 예제 2만 하더라도 int 형의 최대 범위를 훌쩍 넘겨버리기 때문에, `unsigned long long` 타입을 사용해주어야 한다.

 

시간복잡도로는 재귀함수를 수행하고, n만큼 순회를 진행하기 때문에, $O(2^n * n)$만큼 소요된다.

 

코드

/*
임의의 지렁이 두 마리 매칭, 한 지렁이에게 다른 지렁이가 있는곳으로 가도록 하기
가능한 지렁이들이 움직인 벡터 합의 크기가 작기를 바람

지렁이들은 2차원 평면 안에서 이동함. 
a -> b 라면, 그 벡터는 점 a 에서 b를 가리키는 벡터가 된다.
|V| = x * x + y * y

벡터의 합 구하기 : 

풀이 : 조합
- 지렁이는 n / 2마리만 선택해도 된다.
- 벡터의 성질 : 교환법칙, 결합법칙이 성립
- 도착 벡터 - 출발 벡터를 하면 이동거리가 구해진다.

*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define ll unsigned long long
#define INF 800000000002
using namespace std;

int t, n;
vector<pair<int, int>> worms;
int visited[21];
ll ans;

void recur(int depth, int idx) {
	if (depth == n / 2) {
		// 벡터 크기 계산
		ll x = 0, y = 0;
		for (int i = 0; i < n; i++) {
			if (visited[i]) {
				x += worms[i].first;
				y += worms[i].second;
			}
			else {
				x -= worms[i].first;
				y -= worms[i].second;
			}
		}
		ll tmp = x * x + y * y;
		if (ans > tmp)
			ans = tmp;
	}
	for (int i = idx; i < n; i++) {
		if (!visited[i]) {
			visited[i] = 1;
			recur(depth + 1, i + 1);
			visited[i] = 0;
		}
	}
}

int main() {
	cin >> t;
	for (int tc = 1; tc < t + 1; tc++) {
		worms.clear();
		memset(visited, 0, sizeof(visited));
		ans = INF;
		cin >> n;
		for (int i = 0; i < n; i++) {
			int a, b;
			cin >> a >> b;
			worms.push_back(make_pair(a, b));
		}

		recur(0, 0);

		cout << '#' << tc << ' ' << ans << '\n';
	}

	return 0;
}

배운 점 

오랜만에 벡터를 다루는 문제를 만났기 때문에 벡터의 계산 과정을 검색해보았다.

수학적인 접근이 어려웠을 뿐이지, 문제에 접근하는 자체는 어렵지 않은 구현이였다.