정수 X가 주어졌을 때, 0에서 출발하여 X에 도달하기 위해 필요한 최소 점프 횟수를 구하는 문제입니다. 첫 번째 점프의 길이는 반드시 1이며, 그 이후의 각 점프는 바로 앞 점프보다 정확히 1씩 길어집니다. 또한 매 점프마다 왼쪽 또는 오른쪽 어느 방향으로든 이동할 수 있습니다.
예를 들어 X = 8이라면 답은 4가 됩니다. 다음과 같은 경로가 가능하기 때문입니다.
0 → -1 → 1 → 4 → 8
문제 해결의 핵심 아이디어
이 문제를 잘 관찰해 보면 다음과 같은 규칙성을 발견할 수 있습니다.
- 항상 오른쪽 방향으로만 점프했다면, n번의 점프 후에는 p = 1 + 2 + 3 + … + n 위치에 도달하게 됩니다.
- 왼쪽으로도 점프할 수 있다면, k번째 점프를 왼쪽으로 했을 때 최종 위치는 p – 2k가 됩니다. 즉, 한 번의 점프 방향을 바꿀 때마다 총합이 2k만큼 감소합니다.
- 따라서 어떤 점프를 왼쪽으로 하고 어떤 점프를 오른쪽으로 할지 적절히 선택하면, n번의 점프 후 도달할 수 있는 위치는 n(n+1)/2부터 –n(n+1)/2 사이이며, 그 값은 반드시 n(n+1)/2와 같은 홀짝성(짝수/홀수)을 가지게 됩니다.
이 성질을 이용하면, 누적 합이 목표 값 X보다 크거나 같아지고, 동시에 누적 합과 X의 차이가 짝수일 때까지 점프 횟수를 늘려가면 최소 점프 횟수를 구할 수 있습니다.
C++ 구현 예제
#include<iostream>
#include<cmath>
using namespace std;
inline int sumOneToN(int n) {
return (n * (n + 1)) / 2;
}
int jumps(int n) {
n = abs(n);
int ans = 0;
while (sumOneToN(ans) < n or (sumOneToN(ans) - n) & 1)
ans++;
return ans;
}
int main() {
int n = 9;
cout << "Number of jumps: " << jumps(n);
}
코드 설명
- sumOneToN 함수: 1부터 n까지의 합, 즉 n(n+1)/2를 계산하여 반환합니다.
- jumps 함수: 입력값을 절댓값으로 변환한 뒤, 누적 합이 목표값 이상이 되고 그 차이가 짝수가 되는 최소의 점프 횟수를 반복문으로 찾습니다.
- main 함수: 예제 값 9에 대해 결과를 출력합니다.
실행 결과
Number of jumps: 5
X = 9인 경우, 5번의 점프로 목표 지점에 도달할 수 있습니다. 이 알고리즘은 단순 반복문 기반이지만, 수학적 성질을 활용하기 때문에 효율적으로 동작합니다.