LeetCode : 754. Reach a Number

 

문제)

상황 설명 : 무한한 수직선 위에 위치 0에서 시작. 목표 지점은 target 위치.

특정 횟수 numMoves만큼 이동할 수 있다.

각 이동에서 왼쪽이나 오른쪽으로 갈 수 있다.

i번째 이동(i == 1부터 i == numMoves까지) 중에 선택한 방향으로 i 단계를 수행.

목표 : target 위치에 도달하기 위해 필요한 최소 이동 횟수 numMoves를 반환.

 

문제 난이도 : 중

 

소요시간 및 풀이)

무슨 알고리즘을 썻다기 보다 그냥 수학적 접근으로 풀었다.

중 치고는 쉬운 문제.

 

소요 시간 : 14분

 

정답 코드

class Solution 
{
public:
    int reachNumber(int target) 
    {
        target = abs(target);
        int sum = 0;
        int cnt = 0;

        while (sum < target || (sum - target) % 2 != 0) {
            cnt++;
            sum += cnt;
        }

        return cnt;
    }
};