시작점에서 목표 지점까지 이동하는 데 필요한 최소 단계 수를 구하는 C++ 프로그램

좌표 (x, y)가 주어졌을 때, 2차원 격자 위에 있는 로봇이 (0, 0) 위치에서 출발해 (x, y) 지점까지 이동하려고 합니다. 로봇은 위, 아래, 왼쪽, 오른쪽으로 움직이거나 현재 칸에 그대로 머무를 수 있으며, 가능한 한 적은 명령으로 목적지에 도달하는 것이 목표입니다. 이때 필요한 최소 단계 수를 구하는 것이 바로 이 문제의 핵심입니다.

예를 들어 입력이 x = 3, y = 4라면 출력은 7이 됩니다.

풀이 접근 방식

이 문제는 다음 공식 하나로 간단하게 해결할 수 있습니다.

x + y + (|x - y|, |x - y + 1|, |x - y - 1| 중 최솟값)

기본 이동 비용인 x + y에 두 좌표의 차이에 따른 보정값을 더하는 방식입니다. 세 후보 값 가운데 최솟값을 선택함으로써 불필요한 추가 이동 없이 최적의 경로를 계산할 수 있습니다.

예시 코드

아래 C++ 구현을 살펴보면 개념을 더 쉽게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int solve(int x, int y) {
    return x + y + min(abs(x - y), min(abs(x - y + 1), abs(x - y - 1)));
}
int main() {
    int x = 3;
    int y = 4;
    cout << solve(x, y) << endl;
}

실행 결과 확인

x = 3, y = 4를 대입하면 다음과 같이 계산됩니다.

|3 − 4| = 1
|3 − 4 + 1| = 0
|3 − 4 − 1| = 2

세 값 중 최솟값은 0이므로 전체 결과는 3 + 4 + 0 = 7이 됩니다. 이 풀이는 반복문 없이 상수 시간(O(1)) 안에 답을 구할 수 있다는 장점이 있어, 좌표 값이 커져도 성능 저하 없이 즉시 결과를 얻을 수 있습니다.

입력

3, 4