A → B (feat. 백준, 16953번)

A → B
https://www.acmicpc.net/problem/16953

16953번: A → B

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register long long A, B, ans = 1000000000;
    cin >> A >> B;
    queue<pair<long long, long long>> q;
    q.push(make_pair(A, 1));
    while(!q.empty()){
        auto p = q.front(); q.pop();
        auto v = p.first, cnt = p.second;
        if(v == B){
            ans = min(ans, cnt);
            continue;
        }
        else if(v > B){
            continue;
        }
        else{
            q.push(make_pair(v * 2, cnt + 1));
            q.push(make_pair(v * 10 + 1, cnt + 1));
        }
    }
    if(ans == 1000000000)
        cout << -1;
    else
        cout << ans;
    return 0;
}
// *&)*@*

 

반응형

1. A는 A * 2와 A * 10 + 1 로 연산될 수 있습니다.
2. A * 2는 (A * 2) * 2 와 (A * 2) * 10 + 1 로 연산될 수 있습니다.
3. 즉 증가만 가능하고 감소는 불가능하므로 B를 넘어가는 연산은 무시해도 됩니다. 또한 위와 같은 과정을 bfs로 풀이하면서, B가 될때마다 최소 연산 횟수를 구하면 됩니다.