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

문제 설명

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

제한사항

• 숫자 N: 1 이상 10억 이하의 자연수
• 숫자 K: 1 이상의 자연수

---

풀이

5분
이동하려는 거리 부터 순간이동하고, 순간 이동이 불가능하면(즉, 거리가 홀수이면) 칸을 옮기는 방법으로 최소 점프 회수를 구했다.

코드

// 10:54 ~ 10:58

#include <iostream>

using namespace std;

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

    return ans;
}