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

16953번 : A → B

---

문제)

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

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

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

 

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

 

풀이)

 

// 16953. A->B
#include <iostream>
#include <queue>
 
using namespace std;
 
int a, b;
 
// b값이 10억이므로 long long을 사용해야 함
long long bfs(int a)
{
    queue<pair<long long, int>> q;
    q.push(make_pair(a, 0));
 
    while (!q.empty())
    {
        long long a = q.front().first;
        long long d = q.front().second;
        q.pop();
 
        // - 연산이 없으므로 a가 b를 넘어가는 순간
        // 이후 연산은 의미가 없음
        if (a > b) continue;
        if (a == b) return d + 1;
 
        q.push(make_pair(a * 2, d + 1));
        q.push(make_pair(a * 10 + 1, d + 1));
    }
 
    return -1;
}
 
int main()
{
    cin >> a >> b;
    cout << bfs(a);
 
    return 0;
}
 

---

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

16953번: A → B