[알고리즘] Summer/Winter Coding(~2018) - [JavaScript] 점프와 순간 이동

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

프로그래머스

본 포스팅에서 다루는 문제는 위 프로그래머스 링크를 통하여 문제 확인 및 풀이가 가능합니다!

 

 

1.1. 실패 코드(dp)

function solution(n)
{
    let dp = new Array(n+1).fill(0);
    let canTp = false;
    // base case
    dp[0] = 0;
    dp[1] = 1;
    
    for (let i = 2; i < n+1; i++) {
        canTp = (i % 2 === 0);
        
        if (canTp) {
            let costJp = dp[i-1];
            let costTp = dp[i/2];
            
            (costJp < costTp)
                ? dp[i] = costJp
                : dp[i] = costTp;
            
        } else {
            dp[i] = dp[i - 1] + 1;
        }
    }

    return dp[n];
}

채점 결과

정확성: 60.0

효율성: 0.0

합계: 60.0 / 100.0

 

 

1.2. 문제 접근 방법

 이 문제는 최소한의 배터리 사용량으로 목적지에 도달해야 하는 문제입니다. 첫 번째 접근으로는 문제의 해로 최솟값을 구하는 상황이었기 때문에 동적 계획법(Dynamic Programming, DP)를 사용하여 가능한 모든 경우의 수를 계산하려고 시도하였습니다.

 

하지만 이 경우에는 n에 도달하기 위한 배터리 사용량을 구하기 위해서는 Base Case 0, 1을 제외한 2부터 n까지 n - 1번의 주요 연산이 요구되며 O(n)의 시간 복잡도를 가지게 됩니다.

 

 숫자 N은 1 이상 10억 이하의 자연수라는 조건이 있었고 DP가 이 문제의 규모를 감당하기에는 너무 많은 계산량을 필요로 하기 때문에 효율성에서는 전혀 점수를 받지 못한 케이스입니다.

 

2.1. 성공 코드

function solution(n)
{
    let num = n;
    let answer = 1;
    
    while (num !== 1) {
        if (num % 2 === 0) {
            num = num / 2;
        } else {
            answer++;
            num = parseInt(num / 2);
        }
    }
    
    
    return answer;
}

채점 결과

정확성: 60.0

효율성: 40.0

합계: 100.0 / 100.0

 

2.2. 문제 접근 방법

 

 이 문제의 경우에는 입력으로 주어지는 N이 매우 큰 특수한 경우이기 때문에 모든 경우의 수를 따지는 것이 아닌 문제의 규칙을 파악하는 것이 중요했습니다.

 

 문제를 풀이하면서 주목해야 할 점은 텔레포트를 하는 경우에는 배터리를 소모하지 않는다는 것이며, 이는 순간이동을 최대한 많이 사용하는 것이 배터리 사용량이 최소로 만드는 것과 같음을 의미합니다.

 

 이를 위하여 dp와 같은 bottom-up 방식이 아닌 도착점으로부터 출발점 방향으로 역산하여 순간이동이 가능한 경우(짝수인 경우)에는 텔레포트를 수행하도록, 홀수인 경우에는 1칸을 점프하여 순간이동이 가능한 짝수로 변환하는 과정을 반복하였습니다.

 

 이 과정은 num이 1이 될 때까지 반복되며, 점프를 사용한 횟수(answer)가 곧 최소 배터리 사용량이 됩니다.