무한 수선에 수 위치가 있다고 가정합니다. (-inf ~ +inf). 0에서 시작하여 설명된 대로 이동하여 목표에 도달해야 합니다. i번째 이동에서 왼쪽 또는 오른쪽으로 i 단계로 이동할 수 있습니다. 필요한 최소 이동 수를 찾아야 합니다. 목표가 2라고 가정하면 최소 단계는 3이 됩니다. 0에서 1, 1에서 -1, -1에서 2입니다.
이 문제를 해결하기 위해 기억해야 할 몇 가지 중요한 사항이 있습니다. 목표가 음수이면 숫자 라인이 동일하므로 이것을 양수로 간주하십시오. 해결을 위해 아이디어는 가능한 한 한 방향으로 이동하는 것입니다. 따라서 0에서 1로, 1에서 3으로 이동(1 + 2), 3에서 6으로 이동(1 + 2 + 3) 등. 따라서 n번째 이동 후에 대상이 발견되면 이동 횟수를 반환하면 됩니다. 그러나 기준점이 목표보다 크다면 우리는 우리가 얼마나 앞서 있는지의 차이를 찾아야 합니다. 이제 i번째 단계를 뒤로 이동하면 합계가 (합 - 2i)가 된다는 것을 알 수 있습니다. 이제 sum-2i가 목표라면 결과를 얻었습니다. 그러나 그 차이는 짝수일 수도 홀수일 수도 있습니다. 짝수인 경우 결과로 n을 반환하고, 그렇지 않으면 한 단계 더 진행합니다. 따라서 합계에 n + 1을 더하고 이제 다시 차이를 구합니다. n + 1이 대상이면 리턴하고, 그렇지 않으면 n + 2로 한 단계 더 수행합니다.
예시
#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