무한 수선의 위치 0에 서 있다고 가정합니다. 이제 목표 위치에 목표가 있습니다. 여기에서 각 이동에서 왼쪽 또는 오른쪽으로 이동할 수 있습니다. n번째 이동(1부터 시작) 동안 n 단계를 수행합니다. 목적지에 도달하는 데 필요한 최소 단계 수를 찾아야 합니다. 따라서 입력이 target =3과 같으면 2단계가 필요합니다. 0에서 1, 1에서 3.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 대상 :=|대상|, cnt :=0
- 대상> 0,
- cnt 1 감소
- 대상 :=대상 –cnt
- 대상이 짝수이면 cnt를 반환하고, 그렇지 않으면 cnt + 1 + cnt mod 2를 반환합니다.
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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