백준 16953번 A→B // C++

문제

A → B

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

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

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

입력

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

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

---

풀이

bfs 방식의 탐색을 통하여, A가 B가 될 수 있는지 확인한다.

해당 숫자를 작게 만드는 연산은 없기 때문에, 연산 결과가 B보다 큰 경우에는 탐색을 하지 않아도 된다.

1을 가장 오른쪽에 추가하는 연산은 (해당 수 * 10) + 1이다.

또한, B의 최대 값이 10^9인데 임의의 수 X*10가 int 범위를 벗어나는 경우가 생길 수 있으므로, X <= 10^8인 경우에만 10을 곱하는 연산을 하면 int의 범위를 벗어나지 않을 수 있다.

---

코드

#include <iostream>
#include <queue>

using namespace std;

#define MAXNUM 1000000000

int main() {
    int A, B;
    bool finish = false;

    cin >> A >> B;

    queue<pair<int, int>> q;
    q.push(make_pair(A, 1));

    while(!q.empty()){
        int num = q.front().first;
        int count = q.front().second;
        q.pop();

        if(num == B){
            cout << count;
            finish = true;
            break;
        }

        if(num * 2 <= B){
            q.push(make_pair(num * 2, count + 1));
        }
        if (num <= MAXNUM / 10) {
            if (num * 10 + 1 <= B) {
                q.push(make_pair(num * 10 + 1, count + 1));
            }
        }
    }

    if(!finish){
        cout << -1;
    }

    return 0;
}