무한히 뻗어 있는 수직선 위에서 여러분은 위치 0에 서 있다고 가정해 보겠습니다. 그리고 목표 지점인 target이 어딘가에 놓여 있습니다. 매번 이동할 때 왼쪽 또는 오른쪽 어느 방향이든 선택할 수 있으며, n번째 이동(1부터 시작)에서는 정확히 n칸을 이동해야 합니다. 이때 목적지에 도달하기 위해 필요한 최소 이동 횟수를 구하는 것이 이 문제의 핵심입니다.
예를 들어 target = 3이라면 정답은 2입니다. 첫 번째 이동에서 0에서 1로, 두 번째 이동에서 1에서 3으로 이동하면 되기 때문입니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- target := |target|, cnt := 0 으로 초기화합니다.
- target > 0인 동안 반복합니다:
- cnt를 1 증가시킵니다.
- target := target − cnt 로 갱신합니다.
- 반복이 끝난 후 남은 target이 짝수라면 cnt를 반환하고, 홀수라면 cnt + 1 + (cnt mod 2)를 반환합니다.
왜 이 방법이 동작할까요?
같은 방향으로 계속 이동하다가 처음으로 target에 도달하거나 이를 초과하는 순간의 이동 횟수를 cnt라고 합시다. 초과분(남은 target 값)이 짝수라면, 지금까지의 이동 중 하나의 방향을 반대로 뒤집어 총 변위를 2만큼 조정할 수 있으므로 cnt가 곧 정답입니다. 초과분이 홀수라면 한 번(cnt가 홀수일 때) 또는 두 번(cnt가 짝수일 때)의 추가 이동으로 초과분을 짝수로 만든 뒤 같은 논리를 적용하면 됩니다. 또한 좌우 대칭성 덕분에 음수 목표 지점은 절댓값으로 변환해도 결과가 동일합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int reachNumber(int target) {
target = abs(target);
int cnt = 0;
while(target > 0){
target -= ++cnt;
}
return target % 2 == 0? cnt : cnt + 1 + cnt % 2;
}
};
main(){
Solution ob;
cout << (ob.reachNumber(3));
}입력
3
출력
2
마치며
이 알고리즘은 1부터 cnt까지의 합이 target을 처음으로 넘어설 때까지만 반복하기 때문에 시간 복잡도는 O(√target)으로 매우 효율적입니다. 수학적 성질을 활용해 단 몇 줄의 코드로 문제를 해결할 수 있는 대표적인 그리디·수학 유형의 예제이니, 직접 다양한 target 값을 넣어보며 원리를 확인해 보시기 바랍니다.