문제
N명의 사람이 2차원 좌표 위에 있다. 두 사람 사이의 맨해튼 거리(Manhattan distance)가 가장 먼 두 사람의 번호를 출력한다.
맨해튼 거리는 두 점 (x1, y1), (x2, y2) 사이에서 |x1 - x2| + |y1 - y2|로 정의된다.
입력
- 첫 번째 줄: 사람의 수 N
- 이후 N줄: 각 사람의 좌표
xi yi
출력
- 맨해튼 거리가 가장 먼 두 사람의 번호 (1-indexed)
예제
| 입력 | 출력 |
|---|---|
3 1 1 5 5 3 3 | 1 2 |
풀이
모든 두 사람 쌍에 대해 맨해튼 거리를 계산하고, 거리가 최대인 쌍을 찾는다.
- N명의 좌표를 입력받아 배열에 저장한다.
- 이중 반복문으로 모든 쌍
(i, j)의 맨해튼 거리를 계산한다. - 현재까지의 최댓값보다 크면 최댓값과 해당 인덱스를 갱신한다.
- 최댓값을 갖는 쌍의 번호를 출력한다.
핵심 아이디어: 브루트포스로 O(N²) 모든 쌍을 탐색하여 맨해튼 거리 최댓값을 구한다. N이 최대 1000이므로 약 50만 번 연산으로 충분히 시간 제한 내에 처리된다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int g[1002][1002] = {};
int main()
{
int n;
cin >> n;
vector<int> a(n + 1);
vector<int> b(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i] >> b[i];
}
int max = 0, p1 = 0, p2 = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 2; j <= n; j++)
{
if (abs(a[i] - a[j]) + abs(b[i] - b[j]) > max)
{
max = abs(a[i] - a[j]) + abs(b[i] - b[j]);
p1 = i;
p2 = j;
}
}
}
cout << p1 << " " << p2;
}복잡도
- 시간: O(N²) — N명에 대해 모든 쌍을 탐색
- 공간: O(N) — 좌표 저장용 배열