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

문제

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

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

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

입력

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

출력

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

예제 입출력

• 예제 입력 1

2 162

• 예제 출력 1

5
2 → 4 → 8 → 81 → 162

• 예제 입력 2

4 42

• 예제 출력 2

-1

• 예제 입력 3

100 40021

• 예제 출력 3

5

Solution

#include <iostream>

using namespace std;

int main(){
    int A, B;
    cin >> A >> B;
    int answer = 0;
    while(1){
        if(A > B){
            cout << "-1\n";
            break;
        }
        if (A == B){
            cout << answer + 1 << '\n';
            break;
        }
        if (B % 2 == 0){
            B /= 2;
        }
        else if(B % 10 == 1){
            B--;
            B /=10;
        }
        else{
            cout << "-1\n";
            break;
        }
        answer++;
    }
}

A가 B보다 크면 당연히 답을 만들 수 없다. 연산을 하다보면 답의 범위를 넘어가버리는 상황이 생길 수 있다.

연산은 총 두개다. A에 2를 곱하거나, 1을 A의 가장 오른쪽에 추가하거나. 이 두가지를 역으로 한다고 생각해보자.
B에 2를 나누거나, B에 1의 자리에 1이 있을 때 그 녀석을 날려주는 것. 이 두가지가 가능한 지 불가능 한 지를 체크해보면 된다.
어차피 둘 중 하나다. 후자면 2로 나눠지지 않을 것이고 전자면 1의 자리에 1이 있을 수가 없다.
역으로 추적하다보면 가장 최소한의 경우가 나온다.