프로그래머스 - 점프와 순간이동 (C++)

처음엔 최소값을 구하는거고 백준에서 비슷한 워딩의 문제를 본 적이 있어서 BFS인 줄 알았다.

이 문제는 0에서 시작해서 걷거나 순간이동 두가지 조건이 있는것으로 보인다.

그러나 처음 몇 걸음을 걸어야할지 알수없다. 한발짝씩 가서 모든 조건을 새어보는 것은 불가능하다.

그러나 목적지 입장에서 생각해보면 

이전의 수에서

 

x2 되었거나 

+1 되었거나

 

둘중 하나이다. x2는 비용이 0이기 때문에 이왕이면 x2 를 많이 사용해야한다. 그러므로

n이 짝수이면 나누기2

홀수이면 빼기 1 하면서 0까지 얼마나 걸리나 계산하면 된다.

#include <iostream>
using namespace std;

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

    return ans;
}