문제 요약

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

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

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

입력
첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.

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

풀이

A에서 B로 가는 경우의 수는 한 가지가 아니기 때문에 연산량이 많아질 수 있다.
따라서 역으로 B에서 A로 가는 경우의 수를 구한다.
이 경우는 다음과 같은 이유로 최적의 해를 만족한다.

0. 가능한 연산은 2 * A 혹은 10 * A + 1 두가지 밖에 없다.
1. B가 짝수인 경우: 이전 연산에서 A = 2 * A 의 연산이 이루어졌다
2. B % 10 == 1인 경우: 이전 연산에서 A = 10 * A + 1 의 연산이 이루어졌다.
3. 그 외의 경우: 두 연산으로는 불가능한 연산이 이루어졌다.

따라서 역으로 연산을 하게 되면 모든 경우의 수를 포함할 수 있다.
그렇기 때문에 최적의 해를 구할 수 있고, 불가능한 연산인지도 판별가능하다.

코드:

#include <iostream>
using namespace std;

int main()
{
	int a, b, count;

	cin >> a >> b;
	count = 1;
	while (a <= b)
	{
		if (a == b)
		{
			cout << count;
			return (0);
		}
		else if (b % 10 == 1)
			b /= 10;
		else if (b % 2 == 0)
			b /= 2;
		else
			break;
		count++;
	}
	cout << -1;
}