[programmers] 점프와 순간이동

문제 개요

👉 programmers 문제 12980 바로가기

0에서 시작해 목적지(D)에 도달하면 된다. 한 칸씩 앞으로 전진하거나, (현재까지 온 거리) x 2에 해당하는 위치로 텔레포트할 수 있다.
이 때, 한 칸씩 앞으로 전진하는 횟수를 최소로 하는 전진 횟수 N을 구하시오.

예를 들어 D가 5라고 할 때,
ⓐ 1 + 1 + 1 + 1 + 1 = 5
ⓑ (1 + 1) * 2 = 5
ⓒ 1 * 2 * 2 = 5
다음과 같이 3가지 이상의 경우가 있고, 정답은 전진 연산이 가장 적은 ⓒ의 1이 정답이다.

풀이 과정 1

첫째로, BFS를 활용해 최단 경로 체크하는 방법으로 해결하려고 했다.
1차원 Map을 만들고 D에 도달할 때까지 +=1, *=2 연산을 BFS하는 것이다.

하지만 1 <= D <= 1,000,000,000 조건에 의해 불가능함을 알고 포기했다.
이 조건으로 최적해가 있을 것이라는 힌트를 얻을 수 있었다.

풀이 과정 2

텔레포트 연산의 *=2가 이진수의 shift 연산을 연상시켜서, 일단 5를 이진법으로 변경해보았다.

5₍₁₀₎ ………101₍₂₎

그 후, 0을 101로 shift, +1 연산으로 변환하는 과정을 생각해보았다.

ⓐ 0에 1 더하기 ………1₍₂₎
ⓑ 1비트 밀기 ………10₍₂₎
ⓒ 1비트 밀기 ………100₍₂₎
ⓓ 100에 1 더하기 ………101₍₂₎

계산해보니 shift 연산이 1의 개수를 변화시킬 수 없다는 것을 알았고, 이에 따라 D(2)가 가진 1의 개수와, +1 연산의 횟수가 동일하다는 것을 의미했다.

풀이

2진법을 이용한 방법

function solution(n)
{
    return n.toString(2).replace(/0/g, "").length;
}

n을 이진수로 바꿔, 1의 개수를 세면 그것이 전진 연산의 횟수이다.

역산하는 방법

다른 사람들의 풀이를 보았더니, D를 역산하는 방법으로 해결하는 방법이 있었다.
짝수면 /=2, 홀수면 -=1을 반복하며, -1 연산의 횟수를 세는 것이다.

이게 최적해임을 어떻게 접근해 푸신건지, 놀라웠다.

// recursive
function solution(n, c=0)
{
    if (n===0) return c;

    return n % 2 === 0 ? solution(n >> 1, c) : solution(n - 1, ++c)
}

// loop
function solution(n)
{
    if(n == 1) return 1;

    var battery = 0;
    // n을 2로 나눠가며 나오는 나머지의 합
    while(n>0) {
        battery += n%2;
        n = Math.floor(n/2);
    }

    return battery;
}