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

접근법:

0에서 N까지 가는 비용을 계산한다.
N에서 0까지가는 최저비용을 계산하는것과 같다.
점프가 배터리를 소모하니, 최대한 순간이동을 많이한다.
N이 짝수 라면 순간이동을 사용했다.
N이 홀수라면 직전에 점프를 했다.

#include <iostream>
using namespace std;

int solution(int n)
{
    int ans = 1;
    while(n != 1)
    {
        ans += n % 2;
        n /= 2;
    }
    return ans;
}

비트셋을 활용한 방식

코드가 간결하다는 장점이 있지만,

bitset 템플릿 안에 상수를 넣어야 하기 때문에

범위보다 큰 수는 처리가 불가능하다.

#include <iostream>
#include <bitset>
using namespace std;

int solution(int n)
{
    bitset<64> bits(n);
    return bits.count();
}

구명보트[프로그래머스]