Level3. 프로그래머스 점프와 순간 이동 - JavaScript

 

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

 

문제 설명

(현재 이동 거리)*2 순간이동은 이동 비용이 0

현재거리 +1 점프는 이동 비용이 1이다.

 

목표 지점 n까지 가는 최소 비용을 구해야 하기 때문에 최대한 순간이동을 하는게 맞다.

 

처음에는 BFS 최단 거리 구하는 문제인줄 알고 BFS로 구현했다. 

그랬더니 정확성 테스트는 통과 하지만 효율성 테스트를 단 하나도 통과하지 못했다. ㅠㅠ

 

아래는 BFS로 짠 코드이다.

// 1. 순간이동으로 방문 할 수 있는 정점 방문
// 2. 한 칸 이동 
// 3. 1번 부터 반복
function solution(n)
{
    var ans = 0;
    // undefined가 아니면 방문 했고 해당 정점을 방문하기 위해 이동한 거리도 표시
    let dist = [];
    let q = [];
    q.push(0);
    dist[0] = 0;
    while( q.length !== 0 ) {
        let node = q.shift();
        let teleportNode = node*2;
        let jumpNode = node+1;
        if(dist[teleportNode] === undefined && teleportNode <= n) {
            q.push(teleportNode);
            dist[teleportNode] = dist[node];
            if(teleportNode === n ) return dist[teleportNode];
        }
        if( dist[jumpNode] === undefined && jumpNode <= n) {
            q.push(jumpNode);
            dist[jumpNode] = dist[node]+1;
            if(jumpNode === n ) return dist[jumpNode];
        }
    }
    ans = dist[n];
    return ans;
}

 

다시 문제로 돌아와서 해당 문제는 단순 계산으로 해결이 가능하다. 

우리가 가야 하는 목표가 5라고 했을 때

0에서 1로 JUMP로 이동 순간이동으로 2로 그리고 4로이동 다시 JUMP로 5로 이동해서 총 2번의 점프 비용이 2이다.

 

여기서 순간이동을 하는 목표 지점은 항상 짝수이고 홀수 번째는 JUMP로 이동한다. 

그렇다면 출발 지점에서 목표 지점으로 가는 길을 계산하면 고려해야할 요소 가 많으니 

목표 지점에서 출발 지점으로 역으로 계산하면 쉽게 최소비용을 구할 수 있지 않을까 

옛날에 미로 탈출 경로를 찾을 때 탈출 지점에서 시작 지점으로 그려보면 더 잘 풀리는거랑 비슷한 느낌이다. 

 

목표 지점이 5라고 했을 때 5로 순간이동할 수 있는 한 지점은? 없다. 5/2는 나머지 값이 생긴다. 

그렇다면 순간이동을 해서 5로 왔을리는 없으니 4지점에서 JUMP로 도착한것이다.

 

이런 식으로 5 --(JUMP)-> 4 --(순간이동)-> 2 --(순간이동)-> 1 --(JUMP)-> 0 경로가 완성된다.