16953번 A → B

https://www.acmicpc.net/problem/16953

재귀에 약한 것 같다.

다시 풀어볼 문제이다.

복습.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
 
int calc(long long a, long long b)
{
    if (a == b) return 1;
    if (a > b) return -1;
 
    int two = calc(2 * a, b);
    int one = calc(10 * a + 1, b);
 
    // 둘 다 불가능하면, 당연히 -1
    if (two == -1 && one == -1) return -1;
    
    // 둘 중 하나만 가능하면, 다른 방법에 대해 다음 진행을 위해 1을 증가시킨 후 return
    if (two == -1) return one + 1;
    if (one == -1) return two + 1;
 
    // 만약 둘 다 가능하면, 둘 중 더 적은 방법 수에 대해 1을 증가시킨 후 return
    return min(one, two) + 1;
}
 
int main(void)
{
    long long a = 0, b = 0;
 
    cin >> a >> b;
 
    cout << calc(a, b) << '\n';
 
    return 0;
}