1090 - 체커

step 1

모든 칸에 대해서 해당 칸에 체커가 1, 2, ..., $N$개가 있기 위한 최소 이동 횟수를 알면 문제는 쉽게 해결이 가능합니다. 여기서 모든 칸이 아니라 특정 칸으로 줄이려면 어떻게 해야 할까요?

step 2

가로와 세로는 따로 계산할 수 있습니다.

체커가 판에 놓여있다고 해봅시다. 빨간색이 체커입니다. 체커를 기준으로 가로, 세로 선을 그어주었습니다.

만약 아래 그림에서 초록색 위치에 $N$개가 모일 때의 이동 횟수를 구했다고 합시다.

그러면 여기서 초록색 점이 한칸 오른쪽으로 이동했다고 생각해 봅시다.

1. 만약 이동 횟수가 줄었다면 초록 점은 답이 될 수 없습니다.
2. 만약 이동 횟수가 늘었다면 초록 점이 왼쪽으로 갈 때는 이동 횟수가 줄어든다는 뜻입니다. 그렇다면 초록 점은 답이 될 수 없습니다.
3. 만약 이동 횟수가 같다면 초록점을 볼 필요가 없습니다.

만약 초록 점이 세로선에 있다면 이야기는 달라집니다. 하지만 면이나 가로 선 위에 있다면 좌우로 움직였을 때의 이동 횟수가 일정하게 변하기 때문에 위 논리가 적용됩니다. 그리고 이건 위아래에 대해서도 마찬가지입니다. 

그러면 정답 후보는 파란색 점 뿐입니다.

이 점들에 대해 답을 구해주면 됩니다.

코드

#include <stdio.h>
#include <algorithm>
using namespace std;
struct data
{
    int x, y;
} b[60];
int mapp[3000][60];
int main()
{
    int n, i, j, k;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        scanf("%d%d", &b[i].x, &b[i].y);
    }
    int cnt = 0;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            cnt++;
            for (k = 1; k <= n; k++)
            {
                mapp[cnt][k] = abs(b[i].x - b[k].x) + abs(b[j].y - b[k].y);
            }
            sort(mapp[cnt] + 1, mapp[cnt] + n + 1);
            for (k = 1; k <= n; k++)
            {
                mapp[cnt][k] += mapp[cnt][k - 1];
            }
        }
    }
    for (i = 1; i <= n; i++)
    {
        int maxx = mapp[1][i];
        for (j = 2; j <= cnt; j++)
        {
            maxx = min(maxx, mapp[j][i]);
        }
        printf("%d ", maxx);
    }
    return 0;
}