[백준 16953번] A → B (C++)

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

16953번: A → B

---

A → B 문제는 백트래킹으로 해결할 수 있습니다.

단, A와 B의 값이 최대 10억이고, 연산 적용시 21억을 초과할 수 있기 때문에 int형이 아닌 long long형을 사용해야합니다.

 

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

long long a, b, ans = INT_MAX;

void back(int th, long long n){
    if(n == b){
        ans = min(ans, (long long) th - 1);
    }else if(n < b){
        back(th + 1, 2 * n);
        back(th + 1, 10 * n + 1);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> a >> b;
    back(1, a);
    cout << ((ans == INT_MAX) ? -1 : ans + 1);
}