[프로그래머스 Level 2] 점프와 순간 이동 - JavaScript

🔗 문제 링크

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

프로그래머스

✏️ 풀이

function solution(n) {
    let consumption = 0;
    while (n) {
        if (n % 2) {
            n = (n - 1) / 2;
            consumption++;
        } else {
            n /= 2;
        }
    }
    return consumption;
}

순간 이동을 할 때에는 건전지를 사용하지 않으므로 최대한 많이 순간 이동을 해야 한다.만약 이전 위치에서 현재 위치로 순간 이동을 했다면, 현재 위치의 거리는 반드시 짝수가 되어야 한다. 따라서 도착점까지의 거리 n이 짝수면 이전 위치에서 순간 이동 또는 점프로 도착점에 도달할 수 있고, 홀수면 점프로만 도착점에 도달할 수 있다. 이 점을 이용해서 도착점부터 시작점까지 역순으로 최적의 이동 방법을 추적할 수 있다.

 

거리를 2로 나눌 수 있으면 2로 나누고(순간 이동), 나눌 수 없으면 1을 빼기(점프)를 반복하면서 0이 될 때까지 반복한다. 즉, 순간 이동이 가능했던 지점에서는 반드시 순간 이동을 했던 것으로 가정하고, 순간 이동으로 도착하는 것이 불가능한 거리가 홀수인 지점에서는 점프를 했던 것으로 가정하는 것이다. 점프를 할 때에만 consumption을 증가시키면 최소한의 건전지 사용량을 구할 수 있다.

 

※ 이 문제를 dp로 풀려고 하면 효율성 테스트를 통과할 수 없다.

 

✏️ 다른 풀이

function solution(n) {
    return [...n.toString(2)].filter(Number).length;
}

10진수를 2진수로 변환할 때, 2로 계속 나누면서 그 나머지(0 또는 1)를 구하고, 마지막 몫과 나머지들을 역순으로 이어 붙이면 2진수로 만들 수 있다. 이 과정이 마치 순간 이동할 때에는 건전지를 소모하지 않고(0), 1칸 점프할 때 건전지를 1 소모하는 것과 같다. 따라서, 10진수 n을 2진수로 변환한 뒤, 1의 개수를 세면 건전지 소모량과 같다는 것을 알 수 있다. 이 점을 활용하면 훨씬 간단하게 해결할 수 있다.