백준 A -> B [c++]

16953 A -> B 실버 2

문제 링크

문제

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

2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

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

출력

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

풀이

A에서 B로 가는 최소값을 찾는 문제로, 초기값이 A < B 이고 A는 계속 커져 B에 도달하거나 못한다.

BFS를 사용해 모든 경우를 탐색하면서 A가 B보다 커지면 pop한다.

사용할 수 있는 연산인 X2 연산과 오른쪽에 1을 추가하는 연산은 겹칠일이 없다. (2배수를 해서 1의 자리가 1이 나오지 못함)

= visited 안써도 됨.

BFS만 써도 해결되는 문제. (주의 : 결과 값이(cnt) int범위를 초과할 수 있어, long long 사용)

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

long long a, b;

long long bfs()
{
    queue <pair<long long, long long> > q;
    q.push(make_pair(a,0));

    while(!q.empty())
    {
        long long num = q.front().first;
        long long cnt = q.front().second;
        q.pop();

        if(num == b)
        {
            return cnt;
        } else if(num > b)
        {
            continue;
        } else {
            q.push(make_pair(num*2, cnt+1));
            q.push(make_pair(num*10 + 1, cnt + 1));
        }
    }
    return -1;
}

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

    long long answer = bfs();

    if(answer > 0)
    {
        cout << answer + 1 << endl;
    } else{
        cout << -1 << endl;
    }

    return 0;
}

• ps
• bfs