프로그래머스 점프와 순간 이동 (JavaScript)

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12980

문제 풀이

current_location 변수를 하나 설정하여 n에 도달할 때까지 점프, 순간이동을 하여 answer를 구하려고했음

-> 무조건 현재 위치에서 순간이동(현재위치x2)한 값을 이동하는 것으로 최소 값을 구할 수 없음

6으로 간다했을 때

1. (틀림) 순간이동으로 2 -> 4로 이동 후 6으로 가면 최소 값이 3이 나옴

2. 2에서 순간이동을 하지 않고 점프를 한다음(3) 순간이동을 하면 6으로 바로 감 -> 최소 값 2

따라서 0에서 n까지를 구하는 것보다 n에서 0에 도달할 때까지 점프를 최소한으로 하게하면 됨

1. n이 2로 나누어 떨어진다? -> 순간이동이 가능 (n /= 2)

2. n이 2로 나누어 떨어지지 않는다? -> 1칸 점프해야 함(n -= 1)

 

function solution(n)
{
    let answer = 0;
    
    while (n > 0) {
        // 순간이동 할 수 있다 -> 2로 나누어 떨어진다.
        if (n % 2 === 0) {
            n /= 2;
        } else {
            // 1칸 점프해야 함
            n -= 1;
            answer++;
        }
    }
    
    return answer;
}

---

결론

0 -> n이 아닌 n -> 0으로 역으로 접근하는 방법을 생각하면 쉽게 문제를 해결할 수 있음