체커
문제
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;
}
'알고리듬 > 문제' 카테고리의 다른 글
[baekjoon] 1194 (0) | 2023.04.10 |
---|---|
[baekjoon] 12100 (0) | 2023.03.23 |
[baekjoon] 14502 (0) | 2023.03.21 |
[baekjoon] 16234 (0) | 2023.03.20 |
[baekjoon] 21315 (0) | 2023.03.13 |