Lv.2 / 점프와 순간 이동

문제

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

프로그래머스

---

 

코드

#include <iostream>
using namespace std;

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

    return ans + 1;
}

---

 

풀이

순간이동을 최대한 많이 하는 것이 좋다. 즉, x2 가 반복될 수록 좋다는 뜻이다. 그래서 최종 도착지인 n 을 시작이라 생각하고 2씩 나누면서 답을 구해냈다.

 

이때, 2로 나눈 나머지가 1이라면 반드시 1칸은 점프해야하기에 그때마다 1씩 더해주었다.

최종적으로 1에 도착할 것이고 시작점이 0이기에 최종 답에 1을 더하여 반환한다.