[프로그래머스] 12980. 점프와 순간 이동

문제 링크

[프로그래머스] 12980. 점프와 순간 이동

풀이 과정

0 부터 시작해 n 으로 도달하는 Bottom-up 방식이 아닌, 거꾸로 n 으로 0 을 찾아 내려가는 Top-Down 방식을 사용해 문제를 해결했습니다.

n 이 작은 경우에는 Bottom-up 으로 점프 최소 횟수를 구할 수 있습니다.

하지만 n 이 5000인 경우에는, Bottom-up 방식으로는 최소한의 점프 횟수를 쉽사리 생각할 수 없습니다.

Top-down 방식의 아이디어는 2로 나눌 수 있으면 미리 나누자 입니다. 수를 빠르고 크게 줄여가며, -1 연산을 최소화 하자는 생각에서 비롯된 발상입니다.

코드

function solution(n) {
    let cnt = 0;

    while (n != 0) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            n -= 1;
            cnt++;
        }
    }

    return cnt;
}

console.log(solution(5));
// console.log(solution(6));
// console.log(solution(5000));