[BOJ] A → B 16953번 C++

문제

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

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

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

입력

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

출력

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

 

접근 방식

 

간단하게 BFS로 풀면 되겠다는 생각을 했다

원래 하던 방식대로 배열을 놓고 -1로 초기화해서 cnt 값을 구할 생각이였는데

B가 최대 1억이라 배열의 크기가 너무 커졌다

 

그래서 queue를 pair로 현재 값과 카운트 값을 동시에 넣어줌으로 해결했다

 

코드

 

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

queue<pair<ll, ll>> q;
ll A,B;

int main() {
    cin>>A>>B;
    q.push({A,1});

    while (!q.empty()) 
    {
        ll x = q.front().first; 
        ll cnt = q.front().second;
        q.pop();

        if(x == B) {
            cout<<cnt;
            return 0;
        }
        for(auto nxt : {2*x , x*10 + 1}) {
            if(nxt > B) continue;
            q.push({nxt, cnt+1});
        }
    }

    cout<<-1;
    
    
}