문제 개요
두 점 a = (x1, y1)과 b = (x2, y2)가 주어졌다고 가정해 봅시다. 두 점 사이의 맨해튼 거리(Manhattan Distance)는 다음과 같이 정의됩니다.
dist(a, b) = |x1 - x2| + |y1 - y2|
점 a의 좌표가 (0, 0)이고 점 b의 좌표가 (x, y)일 때, 다음 두 조건을 동시에 만족하는 점 c를 찾아야 합니다.
- dist(a, c) = dist(a, b) / 2
- dist(b, c) = dist(a, b) / 2
즉, a와 b 사이의 맨해튼 거리를 정확히 절반씩 나누는 점을 구하는 문제입니다. 만약 그러한 점이 존재하지 않으면 -1, -1을 출력합니다.
예를 들어 입력이 x = 13, y = 7이라면 출력은 6, 4가 됩니다.
풀이 단계
전체 거리는 x + y이므로, 이 값이 홀수라면 정수 좌표를 가진 점 c는 절반 거리인 (x + y) / 2를 가질 수 없습니다. 반대로 x + y가 짝수라면 항상 적절한 점을 찾을 수 있습니다. 이 성질을 이용하면 다음 단계로 문제를 해결할 수 있습니다.
x % 2 == 0 이고 y % 2 == 0 인 경우:
(x / 2, y / 2) 출력
(x + y) % 2 == 1 인 경우:
(-1, -1) 출력
그 외의 경우:
(x / 2, (y + 1) / 2) 출력C++ 구현 예제
더 나은 이해를 돕기 위해 아래 구현 예제를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int x, int y) {
if(x % 2 == 0 && y % 2 == 0)
cout<< x / 2 <<' '<< y / 2 <<endl;
else if((x + y) % 2 == 1)
cout<< -1 <<' '<< -1 <<endl;
else
cout<< x / 2 <<' '<< (y + 1) / 2 << endl;
}
int main() {
int x = 13, y = 7 ;
solve(x, y);
return 0;
}입력
13, 7
출력
6 4
동작 원리
x = 13, y = 7인 경우를 살펴보겠습니다. 두 수가 모두 홀수이므로 마지막 분기에 해당하여 (13 / 2, (7 + 1) / 2) = (6, 4)가 출력됩니다. 실제로 dist((0,0), (6,4)) = 6 + 4 = 10이고, dist((13,7), (6,4)) = 7 + 3 = 10으로, 전체 거리 20의 절반인 10과 정확히 일치합니다.