1007. 벡터 매칭

문제집을 다 풀었으니, 이제 골드2~플레5 중 많이 풀린 문제를 쭉 풀어보려 한다. ``solved.ac``에서 다음의 쿼리를 적용한다.

tier:g2..p5 solved:100..

1007번: 벡터 매칭

---

사실 이 문제는 초보자 시절 감명깊게 읽었던 문제이다. 그땐 5분정도 생각하다가 모르겠어서 패스했던 기억이 난다.

 

$N$개의 점을 각각 한 번씩만 선택해서 $N/2$개의 벡터를 만들고, 만들어진 벡터의 합의 크기의 최솟값을 구하는 문제이다. 단순하게 반복문이나 ``next_permutation()``를 사용하면 시간복잡도가 $O(N!)$이 되어 시간 초과가 난다. 간단한 수학을 적용하면 빠르게 해결할 수 있다.

 

임의의 벡터는 $(dx, ~dy)$ 꼴로 표현할 수 있다. 이때 $dx=x[i]-x[j],dy=y[i]-y[j]~(1 \le i,~j \le N, i \ne j)$이므로, 각 벡터의 $dx$는 하나의 $x$와 하나의 $-x$로 이루어져 있음을 알 수 있다. 따라서 합벡터의 $dx$는 $N/2$개의 $x$와 $N/2$개의 $-x$의 합으로 표현할 수 있다. $dy$도 같은 방법으로 구할 수 있다. 이때 어떤 점의 $x$를 더했다면 $y$도 더해야 하고, $x$를 뺐다면 $y$도 빼야 한다.

 

정리하면, $N$개의 점 중 $N/2$개를 선택하여 $x$좌표와 $y$좌표를 모두 더하고, 선택되지 않은 점의 $x$좌표와 $y$좌표를 각각 빼어 합벡터를 구할 수 있다. $N$이 최대 $20$이므로 총 $\left(\begin{array}{c}n\\ n/2\end{array}\right)$개의 합벡터를 시간 안에 구할 수 있다.

---

드디어 풀었다