[프로그래머스] 점프와 순간 이동 (Javascript)

0에서 n까지 가는 dp문제이다.

처음에는 재귀로 dp 돌렸는데 거리가 n을 초과하거나 비용이 더 작을 때만 진행시켜도 시간 초과났다.

 

거리가 2배인 곳으로 순간이동하는 데 비용이 없어 최대한 순간이동 시켜주는 게 좋으므로 

2의 배수라는 것을 처리해주기 위해 %연산자를 써서 n에서 시작해서 0 까지 가준다.

 

2이 배수가 아닐 때에는 순간이동해서 온게 아니므로 -1로 짝수로 이동해준다.

function solution(n)
{
    var ans = 0;

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

    return ans;
}