문제 개요
무한히 뻗어 있는 수직선(-∞ ~ +∞) 위에서 0부터 출발하여 목표 지점(target)까지 이동하는 문제를 생각해 봅시다. 규칙은 간단합니다. i번째 이동에서는 정확히 i칸만큼 왼쪽 또는 오른쪽으로 움직일 수 있습니다. 이때 목표 지점에 도달하기 위해 필요한 최소 이동 횟수를 구하는 것이 과제입니다.
예를 들어 목표가 2라고 가정해 보겠습니다. 이 경우 최소 3번의 이동이 필요합니다. 0 → 1, 1 → -1, 그리고 -1 → 2의 경로로 이동하면 되기 때문입니다.
핵심 아이디어
이 문제를 효율적으로 해결하기 위해 반드시 기억해야 할 포인트들이 있습니다.
- 음수 목표 처리: 수직선은 원점을 기준으로 좌우 대칭이므로, 목표가 음수라면 양수로 바꾸어 생각해도 결과는 동일합니다.
- 한 방향으로 최대한 전진: 우선 한쪽 방향으로 계속 이동해 봅니다. 0 → 1, 1 → 3(1+2), 3 → 6(1+2+3)처럼 n번째 이동 후의 위치는 누적합이 됩니다.
- 정확히 도달한 경우: n번째 이동 후 위치가 목표와 같다면 n이 곧 정답입니다.
- 목표를 초과한 경우: 현재 위치가 목표보다 크다면 얼마나 초과했는지 그 차이를 확인해야 합니다. 여기서 중요한 관찰은, i번째 이동을 반대 방향으로 바꾸면 총합이 (sum − 2i)만큼 변한다는 사실입니다.
따라서 sum − 2i가 목표와 같아지는 순간 정답을 찾은 것입니다. 이때 차이(sum − target)가 짝수인지 홀수인지에 따라 경우가 나뉩니다. 차이가 짝수라면 그대로 n을 반환하면 됩니다. 차이가 홀수라면 한 번 더 이동합니다. sum에 n+1을 더한 뒤 다시 조건을 확인하고, 그래도 맞지 않으면 n+2만큼 한 번 더 이동하면 결국 원하는 조건을 만족하게 됩니다.
C++ 구현 예제
#include<iostream>
#include<cmath>
using namespace std;
int minStepToTarget(int target) {
target = abs(target);
int sum = 0, min_step = 0;
while (sum < target || (sum - target) % 2 != 0) {
min_step++;
sum += min_step;
}
return min_step;
}
int main() {
int target = 11;
cout << "Minimum step to reach the target is: " << minStepToTarget(target);
}
실행 결과
Minimum step to reach the target is: 5
위 코드는 목표가 11일 때 최소 이동 횟수로 5를 출력합니다. 실제로 1+2+3+4 = 10으로 아직 목표에 미치지 못하지만, 5번째 이동까지 진행하면 누적합이 15가 되고 15 − 11 = 4로 차이가 짝수이므로, 일부 이동의 방향을 조정하여 정확히 목표 지점에 도달할 수 있기 때문입니다.