점프와 순간 이동/C++

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

프로그래머스

점프는 한 칸씩 이동하며 칸당 1만큼 건전지를 사용하고 순간 이동은 건전지를 사용하지 않고 현재까지 온 거리 x 2만큼 이동한다. n만큼 이동할 때 건전지 사용량이 최소가 되는 값 return이므로 n을 2로 나누며 나머지가 1이 될 때마다 answer++해주면 된다.

 

핵심은 순간이동의 x2이다.

 

예시를 들면 표와 같이 된다.(점프는 J, 순간이동은 T)

n = 5	0  (J)> 1 (T)> 2 (T)> 4 (J)> 5	answer = 2
n = 6	0  (J)> 1 (T)> 2 (J)> 3 (T)> 6	answer = 2
n = 5000	0 (J)> 1 (T)> 2 .....624 (J)> 625 (T)> 1250 (T)> 2500 (T)> 5000	answer = 5

 

풀이 방법

1. n을 2로 나눈 나머지가 1이면 answer++

2. n /= 2를 한 뒤 반복

3. 반복이 끝나면 answer 리턴

#include <iostream>
using namespace std;

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

    return ans;
}