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

문제

Summer/Winter Coding(~2018) - 점프와 순간 이동

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

 

 

예시 코드

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

 

풀이

 

이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 구하는 문제입니다.

 

• 앞으로 K 칸 점프할 시, 건전지 사용량은 K입니다.
• (현재 위치 * 2)에 해당하는 위치로 순간 이동할 시, 건전지를 사용량은 0입니다.

 

N = 13인 경우,

0 -> 1 // 점프

1 -> 2 // 순간 이동

2 -> 3 // 점프

3 -> 6 // 순간 이동

6 -> 12 // 순간 이동

12 -> 13 // 점프

 

총 세 번의 점프가 필요합니다.

 

이 과정을 거꾸로 하면 십진수를 이진수로 변환하는 과정과 같습니다.

 

13을 이진수로 변환하는 과정

 

13을 이진수로 변환하면 1101이 됩니다.

 

따라서 N까지 도달하는데 필요한 최소한의 건전지 사용량은, N을 이진수로 변환한 후 1비트의 개수와 같습니다.