정수 X가 있다고 가정합니다. 0에서 X에 도달하는 데 필요한 최소 점프 수를 찾아야 합니다. 첫 번째 점프의 길이는 한 단위가 될 수 있으며 각 연속 점프는 이전 점프보다 정확히 한 단위 더 길어집니다. 각 점프에서 왼쪽 또는 오른쪽으로 갈 수 있습니다. 따라서 X =8이면 출력은 4입니다. 0 → -1 → 1 → 4 → 8이 가능한 단계입니다.
주의 깊게 관찰하면 다음과 같이 말할 수 있습니다.
- 항상 올바른 방향으로 점프했다면 n번 점프한 후 p =1 + 2 + 3 + … + n 지점에 있게 됩니다.
- 왼쪽으로도 점프할 수 있다면 k번째 점프에서 p – 2k 지점에 있게 됩니다.
- 어떤 점프가 왼쪽으로 가고 어떤 점프가 오른쪽으로 가는지 신중하게 선택하면 n번 점프한 후 n(n+1)/2와 –(n*(n+1) / 2 사이의 지점에 있을 수 있습니다. ), n(n+1)/2와 같은 패리티를 사용합니다.
예시
#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);
} 출력
Number of jumps: 5