Intro

프로그래머스 level.2 점프와 순간 이동 에 관한 풀이 및 다른 사람들은 어떻게 풀었는지 살펴보도록 하겠습니다.

문제

OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.

즉 문제를 요약하자면 아래와 같습니다.

• K칸 점프 : 점프한 칸수만큼의 건전지 소모
• 순간 이동 : 현재까지 온 거리의 2배를 이동하지만 건전지 소모 x

접근 방식

저는 이동해야하는 거리 n에서 부터 접근하고자 했습니다.
예를 들어 n = 5000이라고 했을 때 순간이동은 건전지를 사용하지 않고 2배를 이동하기에
n = 5000일 때와 n = 2500일 때는 같은 에너지를 사용합니다.
그렇게 되면 건전지 사용량 = 5000 = 2500 = 1250 = 625
즉 5000칸을 이동할 때와 625칸을 이동할 때의 건전지 사용량은 같게됩니다.

이후에도 같은 방식으로 접근합니다.
625 = 312 * 2 + 1
312 = 156 * 2
156 = 78 * 2
78 = 39 * 2
39 = 19 * 2 + 1
19 = 9 * 2 + 1
9 = 4 * 2 + 1
4 = 2 * 2
2 = 1 * 2
1 = 0 * 2 + 1

즉, 625느 312 * 2 에서 1칸 이동한 것과 건전지 사용량이 같고,
건전지 사용량 = 312 = 156 = 78 = 39과 같이 접근할 수 있습니다.

결론적으로 5000칸을 이동할 동안 사용한 건전지 사용량은 5가 되게 됩니다.
javascript 코드로 구현하게 된다면 아래와 같습니다.

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

다른 풀이

다른 분들의 풀이를 보면서 이해한 내용입니다.

5000 = 2500 * 2 + 0
2500 = 1250 * 2 + 0
1250 = 625 * 2 + 0
625 = 312 * 2 + 1
312 = 156 * 2 + 0
156 = 78 * 2 + 0
78 = 39 * 2 + 0
39 = 19 * 2 + 1
19 = 9 * 2 + 1
9 = 4 * 2 + 1
4 = 2 * 2 + 0
2 = 1 * 2 + 0
1 = 0 * 2 + 1

위에 있는 식을 봤을 때 굉장히 많이 본 모양일 것입니다.
바로 이진법으로 변환할 때의 식과 같습니다.
5000을 이진법으로 변환하면 1001110001000으로 변환할 수 있고, 바로 이 이진법에서 1의 갯수가 k와 같습니다. 그렇다면 아래와 같이 간단하게 풀 수 있겠네요 :)

function solution(n) {
    return n.toString(2).replaceAll('0','').length
}