[baekjoon] 1090

체커 

문제

N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 움직이는 것이다.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 체커의 x좌표와 y좌표가 주어진다. 이 값은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 수 N개를 출력한다. k번째 수는 적어도 k개의 체커가 같은 칸에 모이도록 체커를 이동해야 하는 최소 횟수이다.

예제 입력

4
15 14
15 16
14 15
16 15

예제 출력 

0 2 3 4

 

풀이

 체커를 최소로 이동시켜 k개의 체커가 같은 칸에 모이도록하는 좌표는 체커들 내부에 있음으로

체커들로 만들 수 좌표의 순서쌍을 모두 대입하여 최소 거리를 찾는다.

 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

struct xy{
    int x;
    int y;
    double distance;
};

bool compare(const xy& p1, const xy& p2){
    return p1.distance < p2.distance;
}

long long solve(int n, int k, xy board[])
{
    long long *distance = new long long[n];
    long long minimum = 99999999;
    for(int x = 0; x < n; x++)
    {
        for(int y = 0; y < n; y++)
        {
            for(int l = 0; l < n; l++){
                distance[l] = abs(board[l].x - board[x].x) + abs(board[l].y - board[y].y);
            }
            sort(distance, distance+n);
            int sum = 0;
            for(int i = 0; i < k+1; i++)sum += distance[i];
            if(minimum > sum)minimum = sum;
        }

    }
    return minimum;

}

int main()
{
    int n;

    cin >> n;

    xy * board = new xy[n];

    for(int i = 0; i < n; i++)
    {
        cin >> board[i].x;
        cin >> board[i].y;
    }

    for(int i = 0; i < n; i++)
    {
        cout << solve(n, i, board) << " ";
    }
    return 0;
}