[백준] 16953.cpp : A -> B

www.acmicpc.net/problem/16953

16953번: A → B

---

• 10억개의 DP 배열을 다 만들기는 어렵다.
• 최솟값을 구하는데에는, 목표값까지 BFS 를 통해 탐색해나갈 수 있다.
• A 와 B 가 10억 이하의 값이므로, 1을 오른쪽에 추가하는 연산의 경우 unsinged int 로도 오버플로우가 나기 때문에 long long 자료형을 써주도록 한다.

---

#include <iostream>
#include <queue>

using namespace std;

unsigned long long a, b, cur;                   // 자료형에 따른 오버플로우 주의할 것
int count = 1;					// 연산의 최솟값에 1을 더한 값 -> 1부터 시작한 값

int main(void)
{
    cin >> a >> b;

    queue<unsigned long long> q;
    q.push(a);

    while(q.size())
    {
        int size = q.size();
        for(int i = 0 ; i < size ; i++)         // 연산의 최솟값 별로 bfs 탐색
        {
            cur = q.front();
            q.pop();
            if(cur > b) continue;               // 가능한 연산이 모두 단조 증가이므로, b 보다 큰 수 중에서는 b로 갈 수 없다
            if(cur == b)
            {
                cout << count << endl;          // b에 도착했을 경우, 연산의 최솟값을 출력해주고 프로그램 종료
                return 0;
            }
            q.push(cur * 2);                    // 2를 곱한 수
            q.push(cur * 10 + 1);               // 오른쪽에 1을 추가한 수
        }
        count++;
    }

    cout << -1 << endl;                         // B로 정상적으로 도착하지 못했을 경우
}