[백준 C/C++] 16953번 - A → B

문제

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

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

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

---

입출력

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

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

---

풀이

A -> B 과정을 역산한다고 생각하면서 풀면 편하다.

B의 끝자리가 1일 때는 끝자리를 빼주고, B가 2로 나눠떨어질 때는 2로 나눠주면 된다.

 

#include <cstdio>

using namespace std;

int main() {
    int a,b;
    int count=1;
    scanf("%d %d", &a, &b);

    while(true)
    {
        if (a==b)
        {
            printf("%d", count);
            return 0;
        } else if (a>b) {
            printf("-1");
            return 0;
        } else if (b%10==1)
        {
            b = b/10;
            count++;
        } else if (b%2==0)
        {
            b = b/2;
            count++;
        } else {
            printf("-1");
            return 0;
        }
    }
}