step 1
더보기
모든 칸에 대해서 해당 칸에 체커가 1, 2, ..., $N$개가 있기 위한 최소 이동 횟수를 알면 문제는 쉽게 해결이 가능합니다. 여기서 모든 칸이 아니라 특정 칸으로 줄이려면 어떻게 해야 할까요?
step 2
더보기
가로와 세로는 따로 계산할 수 있습니다.
체커가 판에 놓여있다고 해봅시다. 빨간색이 체커입니다. 체커를 기준으로 가로, 세로 선을 그어주었습니다.
만약 아래 그림에서 초록색 위치에 $N$개가 모일 때의 이동 횟수를 구했다고 합시다.
그러면 여기서 초록색 점이 한칸 오른쪽으로 이동했다고 생각해 봅시다.
- 만약 이동 횟수가 줄었다면 초록 점은 답이 될 수 없습니다.
- 만약 이동 횟수가 늘었다면 초록 점이 왼쪽으로 갈 때는 이동 횟수가 줄어든다는 뜻입니다. 그렇다면 초록 점은 답이 될 수 없습니다.
- 만약 이동 횟수가 같다면 초록점을 볼 필요가 없습니다.
만약 초록 점이 세로선에 있다면 이야기는 달라집니다. 하지만 면이나 가로 선 위에 있다면 좌우로 움직였을 때의 이동 횟수가 일정하게 변하기 때문에 위 논리가 적용됩니다. 그리고 이건 위아래에 대해서도 마찬가지입니다.
그러면 정답 후보는 파란색 점 뿐입니다.
이 점들에 대해 답을 구해주면 됩니다.
코드
더보기
#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;
}
'PS - 알고리즘' 카테고리의 다른 글
16570 - 앞뒤가 맞는 수열 (0) | 2024.07.11 |
---|---|
10523 - 직선 찾기 (0) | 2024.07.11 |
30294 - Flea (1) | 2024.07.05 |
14679 - 영우와 ‘갓4’ (0) | 2024.07.05 |
11401 - 이항 계수 3 (0) | 2024.07.05 |