[7571] 점모으기

출처 : 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 \mathbb{M}-\{M\},\mathbb{M}=\{1,2,3,...,M\}$에 대하여

$$\begin{array}{rl}& 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{array}$$

이고

$$f(x_{k+1})-f(x_k)=(2k-M)(x_{k+1}-x_k)$$

가 된다.

그런데 $x_{k+1}\ge x_k$ 이므로,

$$\{\begin{array}{ll}f(x_{k+1})-f(x_k)\le 0,& \text{if 2k }\le \text{ M}\\ f(x_{k+1})-f(x_k)\ge 0,& \text{if 2k }>\text{ M}\end{array}$$

가 되므로 $f(x_k)$가 최소가 되는 $k=\lfloor \frac{M}{2}\rfloor$ + 1 이 된다.

한편,

$x\in [x_k,x_{k+1})$ 에 대해

는상수

$$f^{\prime }(x)=c_k,(c_k는상수)$$

이므로 $f(x)$가 최소가 되는 $x$를 찾기 위해 $x_k$만 고려하면 된다는 사실을 알 수 있다.

따라서 $f(x)$가 최소가 되는 $x=x_{\lfloor \frac{M}{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;
}