이번 문제는 DFS 알고리즘을 재귀적으로 구현하여 해결했다.

• 정수A를 2로 곱할 수도 있고, 10을 곱한 뒤에 1을 더할 수도 있다.
• DFS 함수 안에서 x2와 x10+1을 DFS로 재귀호출 한다.
• result에는 임의의 큰 값을 넣고, result에는 더 작은 cnt값이 들어간다.
• result가 마지막에도 임의의 큰 수라면 A가 B로 될 수 없다고 판단하고 -1을 출력한다.

Code

#include <iostream>
#include <algorithm>
#define MAX 1000000
using namespace std;

long long a, b;
long long cnt=1;
long long result=MAX;


void Input(){
    cin>>a>>b;
}

void DFS(long long n, long long cnt){
    if(n==b){
        result=min(cnt, result);
    }
    if(n>b)
        return;
    DFS(n*2, cnt+1);
    DFS((n*10)+1, cnt+1);
}

void Solution(){
    DFS(a, cnt);
    if(result==MAX){
        cout<<-1<<endl;
    }
    else{
        cout<<result<<endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    return 0;
}

이번에 또 수의 범위를 신경쓰지 않고 int형으로 사용했다가 오답처리를 당했다. 수의 범위를 신경쓰며 구현하자.