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

---

🔗 문제 링크

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

프로그래머스

---

728x90

👩‍💻 코드

#include <iostream>
using namespace std;

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

    return ans;
}

---

📝 풀이

우선 0부터 N까지 가는 것을 N부터 0까지 간다고 생각한다.

건전지를 최소로 사용하려면 순간이동을 최대한 활용해야 한다.

순간이동은 0부터 N까지 갈 때 *2, 반대로 N부터 0까지 갈 때는 /2가 된다.

순간이동을 반복하는 도중 N이 홀수인 경우는 순간이동(/2)을 할 수 없으니 점프(-1)를 해야한다.

점프가 필요할 때 ans를 증가시키고 반복문이 종료된 후 ans을 return 한다.