[C++] 백준 16953 : A → B

백준 16953 : A → B

 

문제 링크

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

16953번: A → B

 

 

문제 내용

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

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

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

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

 

 

Idea

A에서 B가 되기 위한 연산은 두 가지밖에 없다. 따라서 아래와 같은 알고리즘으로 풀었다.

 

1. 2를 곱하거나 1을 수의 가장 오른쪽에 추가하므로, 일의 자리 숫자가 1을 제외한 홀수는 무조건 만들 수 없다. (line 13 ~ line 17)
2. 그 외의 상황에서는 큐를 이용한 bfs를 사용하여 판단해준다.
3. bfs를 탈출할 경우 해당 숫자를 만들 수 없다는 의미 이므로 -1을 출력해준다.

 

 

Code

#include <stdio.h>
#include <queue>
using namespace std;
 
int main()
{
    long a, b;
 
    //input
    scanf("%ld %ld", &a, &b);
 
    //예외 처리
    if (b % 10 != 1 && b % 10 % 2 == 1)
    {
        printf("-1\n");
        return (0);
    }
 
    //큐 <현재숫자, count>
    queue<pair<long, int>> q;
    q.push({a, 1});
    //bfs
    while (!q.empty())
    {
        long num = q.front().first;
        int cnt = q.front().second;
        q.pop();
 
        long first = num * 2;
        long second = num * 10 + 1;
        if (first == b || second == b)
        {
            printf("%d\n", cnt + 1);
            return (0);
        }
        if (first < b)
            q.push({first, cnt + 1});
        if (second < b)
            q.push({second, cnt + 1});
    }
    printf("-1\n");
    return (0);
}