출처 : https://www.acmicpc.net/problem/7571
행의 크기와 열의 크기가 각각 N인 격자공간에 M개의 점이 있다. N = 4이고 M = 4인 경우의 예가 아래에 있다. 격자공간 왼쪽의 숫자는 행 번호이며, 위의 숫자는 열 번호를 나타낸다. 그리고 격자공간내의 각 사각형의 위치는 (행 번호, 열 번호)로 표시한다
이제 격자공간에 있는 모든 점들을 하나의 사각형 안으로 모으려고 한다. 어떤 점을 움직일 때는 그 점이 들어있는 사각형에서 상하좌우로 인접한 사각형으로만 움직일 수 있다.
여기에서는 격자공간내의 한 사각형으로 모든 점들을 모을 때 각 점이 움직인 거리의 합을 고려한다. 예를 들어, 위의 점들을 (3,2)에 있는 사각형으로 모을 때 최단거리로 점들을 이동시킨다면 (1,2)에 있는 점의 이동거리는 2이고, (3,1)과 (4,2)에 있는 점의 이동거리는 각각 1이며, (1,4) 에 있는 점의 이동거리는 4이므로 점들이 움직인 거리의 합은 8이다. 또, 위의 모든 점들을 (1,2)의 위치로 모을 때도 점들이 이동한 거리의 합이 8 임을 알 수 있다. 위의 예에서는 점들을 어떤 하나의 사각형으로 모을 때 이동거리의 합이 8보다 작게 되는 사각형은 없다.
이 문제는 주어진 격자공간에 있는 모든 점들을 하나의 사각형으로 모을 때 드는 이동거리의 합의 최솟값을 구하는 것이다. 주어진 격자공간에서는 하나의 사각형에 여러 개의 점들이 들어 있을 수도 있고, 점들을 모을 때는 어떤 점이 들어 있는 사각형으로도 모을 수 있다고 가정한다.
당연히 완전탐색으로 풀려고 하면 시간초과가 나게 된다. 문제를 재정의 해보면 아래와 같다.
$$\sum_{i=1}^{M} {(|x - x_i| + |y - y_i|)}$$
가 최소가 되는 \(x\), \(y\) 를 찾아라.
그리고 \(x\), \(y\)는 서로 독립적이므로
$$\sum_{i=1}^{M} {(|x-x_i|)}$$
가 최소가 되는 \(x\)를 찾고
$$\sum_{i=1}^{M} {(|y-y_i|)}$$
가 최소가 되는 \(y\)를 찾으면 된다.
결론부터 말하면 \(x\)는 \(x_i\) 들의 중앙값이고, \(y\)또한 마찬가지로 \(y_i\) 들의 중앙값이다.
실제로 중앙값이 해답이 되는지 수학적으로 증명해보자.
우선 \(x_1 \le x_2 \le x_3 \le ... \le x_M\) 라고 가정하자.
그리고
$$f(x) = \sum_{i=1}^{M} {|x-x_i|}$$
라고 하자.
그러면 임의의 \(k \in \Bbb M-\{M\}, \Bbb M=\{1, 2, 3, ... , M\}\)에 대하여
$$
\begin{align}
&f(x_k) = (x_k - x_1) + ... + (x_k - x_k) + (x_{k+1} - x_k) + (x_{k+2} - x_k) + ... + (x_M - x_k)\\
&f(x_{k+1}) = (x_{k+1} - x_1) + ... + (x_{k+1} - x_k) + (x_{k+1} - x_{k+1}) + (x_{k+2} - x_{k+1}) + ... + (x_M - x_{k+1})
\end{align}
$$
이고
$$f(x_{k+1}) - f(x_k) = (2k-M)(x_{k+1} - x_k)$$
가 된다.
그런데 \(x_{k+1} \ge x_k\) 이므로,
$$\begin{cases}
f(x_{k+1}) - f(x_k) \le 0, &\text{if 2k \(\le\) M} \\
f(x_{k+1}) - f(x_k) \ge 0, &\text{if 2k \(\gt\) M}
\end{cases}$$
가 되므로 \(f(x_k)\)가 최소가 되는 \(k = \lfloor{M \over 2}\rfloor\) + 1 이 된다.
한편,
\(x \in [x_k, x_{k+1})\) 에 대해
$$f'(x) = c_k, (c_k는 상수)$$
이므로 \(f(x)\)가 최소가 되는 \(x\)를 찾기 위해 \(x_k\)만 고려하면 된다는 사실을 알 수 있다.
따라서 \(f(x)\)가 최소가 되는 \(x=x_{\lfloor{M \over 2}\rfloor + 1}\) 가 된다.
위와 같이 주어진 좌표들의 X, Y 들의 중앙값이 주어진 문제의 답이 된다. 코드는 아래와 같다.
#include <cstdio>
#include <algorithm>
#define M 100001
using namespace std;
int n, m, tx, ty, s, i;
int x[M], y[M];
int main(){
scanf("%d %d",&n, &m);
for(i = 0; i < m; i++){
scanf("%d %d", &x[i], &y[i]);
}
sort(x, x+m);
sort(y, y+m);
tx = x[m/2];
ty = y[m/2];
for(i = 0; i < m; i++){
s = s + abs(x[i]-tx) + abs(y[i]-ty);
}
printf("%d\n",s);
return 0;
}