A → B C++ - 백준 16953

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

이 문제는 dp로 접근했다가 오랜시간을 붙잡고 있었다.

그래서 bfs로 다시 코드를 짰다.

long long 을 사용하지 않아서 런타임 에러가 났다.

코드는 다음과 같다.

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

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

int main(){
    cin >> A >> B;
    q.push({A,1});
    while(!q.empty()){
        pair<ll, ll> x=q.front();
        if(x.first==B) break;
        q.pop();
        if(2*x.first<=B) q.push({2*x.first, x.second+1});
        if(10*x.first+1<=B) q.push({10*x.first+1, x.second+1});
    }
    if(!q.empty()) cout << q.front().second;
    else cout << -1;
}