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

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

순간이동을 하면 현재까지 간 거리의 두 배에 해당하는 거리에 도착할 수 있고, 에너지를 사용하면 K만큼 이동할 수 있다.
N에 도착하기 위해 최소로 사용하는 에너지가 몇인지를 반환하면 된다.

순간이동을 최대한 많이 해야하므로 N부터 1까지 역으로 가면서 만약 짝수라면 순간이동을 하고, 홀수라면 1을 이동한다.

예를 들어 5000의 경우
5000 -> 2500 -> 1250 -> 625 -> 624 -> 312 -> 156 -> 78 -> 39 -> 38 -> 19 -> 18 -> 9 -> 8 -> 4 -> 2 -> 1 -> 0
으로 이동하기 때문에 총 5번의 이동만 하고, 그 외에는 모두 순간이동으로 움직일 수 있다.

풀고 다른 사람의 코드를 봤는데 __builtin_popcount 라는 신박한 빌트인함수로 푼 사람이 있었다. 이는 x에서 1인 비트가 몇개인지를 반환해주는 것인데, 위에서 말한 방식이 결국 주어진 N에서 1인 비트가 몇개인지를 구하는 방식이다.

코드는 아래와 같다.

#include <iostream>
using namespace std;

int solution(int n)
{
    int ans = 0;
    while(n) {
        if(n % 2) {
            n--;
            ans++;
        } else {
            n /= 2;
        }
    }
    return ans;
}

// __builtin_popcount 방식
#include <iostream>
using namespace std;

int solution(int n)
{
    return __builtin_popcount(n);
}