A → B 16953

문제

접근 방법

숨바꼭질 문제와 유사하다.
B의 과정은 기존 수에서 10배가 되기에 10^9의 경우 8번 정도 이루어질 것이다.
2를 곱하는 경우는 10억의 경우면 2^30 정도이기에 많은 경우를 탐색한다고 볼 수는 없다.
BFS로 2를 곱하는 경우와 1을 오른쪽에 추가하는 경우를 해주면서 B와 같은 값이면 횟수를 출력해 주는 방식을 택하면 된다.

코드

#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
struct node
{
    ll num;
    int cnt;
};
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int A, B;
    cin >> A >> B;
    queue<node> q;
    q.push({A, 1});
    while (!q.empty())
    {
        node cur = q.front();
        if (cur.num == B)
        {
            cout << cur.cnt;
            return 0;
        }
        q.pop();
        // 2를 곱한다.
        ll next1 = cur.num << 1;
        if (next1 <= B)
            q.push({next1, cur.cnt + 1});
        // 1을 수의 가장 오른쪽에 추가한다.
        ll next2 = cur.num * 10 + 1;
        if (next2 <= B)
        {
            q.push({next2, cur.cnt + 1});
        }
    }
    cout << -1;
    return 0;
}

풀이

원래는 map을 활용했는데 (배열의 범위를 넘는다) 다른 사람보다 시간이 더 나왔다. 큰 범위를 탐색하는 것이 아니고 중복되는 수가 나올 가능성이 적기에 빠르게 확인만 해주면 되는 것 같다.

다른 사람의 풀이를 보니 BFS 말고도 B에서 시작하여 A로 가는 방법도 볼 수 있었다.
B에서 1을 빼주고 10을 나누는 것을 우선으로 하여서 수를 줄여나가면 되는 것이다.
즉 그리디하게 풀어주는 것이다.