좌표 평면 위의 한 점 (x, y)와 정수 n이 주어졌을 때, 정확히 n번의 이동으로 원점 (0, 0)에서 해당 좌표까지 도달할 수 있는지 확인해야 합니다. 이동은 상하좌우 네 방향 중 어느 방향으로든 가능하며, 한 번의 이동으로 한 칸씩 움직입니다.
예를 들어, 목표 지점이 p = (2, 1)이고 n = 3이라면 결과는 True입니다. 오른쪽으로 두 번, 위로 한 번 이동하면 총 3번의 이동으로 목표 지점에 도달할 수 있기 때문입니다.
문제 해결 접근법
이 문제는 다음 두 가지 조건만 확인하면 간단하게 해결할 수 있습니다.
- 최소 이동 횟수 확인: 원점에서 (x, y)까지 도달하는 데 필요한 최소 이동 횟수는 맨해튼 거리(Manhattan Distance), 즉 |x| + |y|입니다. 따라서 n이 이 값보다 크거나 같아야 합니다.
- 패리티(짝홀수) 확인: 남은 이동 횟수인 n − (|x| + |y|)가 반드시 짝수여야 합니다. 한 방향으로 나갔다가 되돌아오면 항상 2칸씩 소모되기 때문에, 남은 횟수가 홀수라면 아무리 이동해도 정확히 n번으로 도달할 수 없습니다.
두 조건을 모두 만족하면 True를 반환하고, 하나라도 만족하지 않으면 False를 반환합니다.
구현 예제
다음 코드를 통해 더 자세히 이해할 수 있습니다.
def solve(p, n): if n >= abs(p[0]) + abs(p[1]) and (n - (abs(p[0]) + abs(p[1]))) % 2 == 0: return True return False p = (2, 1) n = 3 print(solve(p, n))
입력
(2, 1), 3
출력
True