백준 16953 A->B C++

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

16953번: A → B

---

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

---

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

---

#include <iostream>
using namespace std;

typedef long long ll;
ll a,b;
ll ans = 9987654321;
ll min(ll a,ll b){
    if(a<b){
        return a;
    }
    else{
        return b;
    }
}
 
void input(){
    cin >> a >> b;
 
}
 
void dfs(ll n,ll start){
    if(n >= b){
        if(n == b){
            ans = min(ans,start);
        }
        return;
    }
    dfs(n*2,start+1);
    dfs(n*10 + 1,start+1);
}
 
int main(void){
    input();
    dfs(a,0);
    if(ans == 9987654321){
        cout << -1;
        return 0;
    }
    else{
        cout << ans + 1;
        return 0;
    }
}

 

주의 할 점 -> int가 아니라 long long을 사용해야 한다.

dfs시 n이 9억이면 n*10 + 1을 하면 90억 + 1이 되면서 오버플로우가 일어난다.

 

기저조건은 n이 b이상일 경우이고, n이 b이면 최소값을 갱신하도록 하였다