[백준 BOJ] 1007. 벡터 매칭
03 Sep 2021난이도
Gold II
문제 풀이
문제 이름부터 뭔가 수학스럽다. 그래서 수학적으로 접근을 해보자.
집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다.
간단하게 설명해보자면, 어떤 집합 P의 벡터매칭은 그 집합의 모든 원소들을 한번씩 사용해 만들어진 벡터들의 집합이라는 것이다. 우리가 구해야하는 것은 이 벡터매칭에 있는 벡터들의 합의 길이의 최솟값이다. 벡터매칭의 벡터들을 모두 다 더했을때, 그 합벡터의 크기가 어떻게 하면 최소가 되느냐를 묻는 것이다.
간단히 생각하면, 모든 벡터매칭 집합들을 다 만들어서 최솟값을 구하면 답이 나온다. 두 점씩 잡아 벡터를 만들어 합벡터에 더하고 하는 식으로 하면 물론 답은 나올 것인데, 그게 좀 복잡하고 생각하기 어려운것 같아서 살짝 다른 관점에서 보면 어떨까? 만들어서 더하는게 아니고 그냥 합벡터 그 자체를 한번 생각해보자.
\[\small \overrightarrow{P}= \left ( \sum_{} x_{i}, \sum_{} y_{i} \right )\]
벡터의 x성분은 x성분대로 더하고, y성분은 y성분대로 더하면, 그게 합벡터이다. 근데, 이걸 조금만 뜯어서 살펴보면,
\[\small \overrightarrow{P} = \left ( \sum_{a}x_{a} - \sum_{b}x_{b},\sum_{a}y_{a} - \sum_{b}y_{b} \right )\]
위 수식처럼 쓸 수 있다. 여기서 a는 어떤 벡터의 끝점에 해당하는 것이고, b는 어떤 벡터의 시작점에 해당하는 것이라 생각하면, 자연스럽게 그 의미를 파악 할 수 있다. 벡터를 만들때, 끝점에서 시작점을 빼서 표현하는데(정확히는 끝점을 가르키는 벡터에서 시작점을 가르키는 벡터의 차) 그것을 그대로 쓴 것이다.
먼저, 끝점과 시작점의 개수는 동일하므로 a = b이고 a = b = n / 2 인 것을 간단하게 파악할 수 있다. 저 식에 의하면, 그냥 a = n / 2개의 점들만 결정해주면 b는 알아서 결정되니, 끝점들만 선택해주는 것으로 벡터를 결정할 수 있음을 알 수 있다. 즉, n / 2개의 점만 결정해준다면 벡터를 쉽게 만들 수 있다.
이때, n는 문제에서 최대 20이라 주어졌기에, 최대 \(\scriptsize C(20, 10)\)가지의 경우의 수가 존재하게 된다. 이 숫자는 대충 \(\scriptsize 1.8 \cdot 10 ^ {5}\)정도 이기에 충분히 시간내에 풀 수 있다.
const double INF = 987654321.0;
double solve(vector<pair<double, double>>& seq, vector<bool> chosen, int cnt, int size, int startIdx) {
//base
if(cnt == size / 2) {
double frontX = 0, backX = 0, frontY = 0, backY = 0;
for(int i = 0; i < size; ++i) {
if(chosen[i]) {
frontX += seq[i].first;
frontY += seq[i].second;
}
else {
backX += seq[i].first;
backY += seq[i].second;
}
}
double X = frontX - backX;
double Y = frontY - backY;
return sqrt(pow(X, 2) + pow(Y, 2));
}
//combination
double ret = INF;
for(int i = startIdx; i < size; ++i) {
if(!chosen[i]) {
chosen[i] = true;
ret = min(ret, solve(seq, chosen, cnt + 1, size, i));
chosen[i] = false;
}
}
return ret;
}
n / 2개의 점을 선택해 합벡터를 구하고 그 크기의 최솟값을 구하는 코드이다. 먼저, seq는 좌표값이 들어있는 벡터이고, chosen은 몇 번째의 좌표점이 선택되었는지 나타내어주는 bool형 벡터이다. 기저사례는 n / 2개의 점이 선택된 경우이니, 그 때 합벡터를 계산해서 값을 구해 리턴해주면 되는 것이다. 그 이외의 경우에는 점들을 선택해 조합을 만들어나가도록 코드를 짜면 해결된다.
나는 처음에 시간초과를 받았는데, 처음 제출한 코드에는 startIdx라는 파라미터가 없었기 때문이다. 이 파라미터가 해주는 일은 앞에서 선택했던 원소들을 거르고 뒤에서부터 선택을 해주게 한다. 이게 없으면.. 같은 경우를 매우 많이 조사하기 때문에, 시간복잡도가 지수적으로 늘어나게 된다. 이 파라미터를 사용해 범위를 제한해 준다면, 시간복잡도는 \(\scriptsize O(C(N, \frac {N} {2}) \cdot T)\)이다. N는 점의 개수이고, T는 테스트케이스 개수이다.
조합을 짤 때에는 항상 의도한 시간복잡도를 가지는지 체크해볼 필요가 있는 듯 하다.. 그렇지 않으면, 나처럼 뻘짓하고 있을테니 유의.