C++ / 프로그래머스 / 점프와 순간 이동

문제

 

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

프로그래머스

문제풀이

 

현재 온 거리 x2 하는 점프는 건전지 사용량이 들지 않는다.

따라서 x2 하는 점프를 많이 해야 한다.

0부터 하게 되면 어느 순간에 해야 효율적인지 알 수 없으므로 거꾸로 해야 한다.

n을 2로 계속 나누면서 홀수가 되면 -1을 하고 n이 0이 될 때까지 계속 반복한다.

 

예를 들어 n이 6이라 해보자.

6 -> 3, 3은 홀수 이므로 -1

2 -> 1, 1은 홀수이므로 -1

다시 0부터 보면 0->1 (+1 점프), 1->2 (x2 점프), 2->3 (+1 점프), 3->6 (x2 점프)

따라서 6인경우 최저 건전지 사용량은 2이다.

 

코드

using namespace std;

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

    return cnt;
}