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

링크

---

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

문제

---

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

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

입력

---

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

출력

---

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

풀이

---

B의 값에 따라 갈라지는 경우를 생각하였다.
1) 짝수인 경우
그 전단계 연산에서 무조건 x2를 하였다.
2) 일의 자리 값이 1인 경우
그 전단계 연산에서 무조건 1을 붙였다.
3) 일의 자리 값이 1이 아닌 홀수인 경우
A에서 B로 만들 수 없는 값이다.

위의 경우들을 생각하여 B를 A로 만들어냈다.

코드

---

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int A, B;
	cin >> A >> B;
	
	int result = 1;

	while (1) {
		if (A == B)
			break;
		else if (A > B) {
			result = -1;
			break;
		}
		if (B % 10 == 1) {
			B /= 10;
			result++;
		}
		else if (B % 2 == 0) {
			B /= 2;
			result++;
		}
		else {
			result = -1;
			break;
		}
	}

	cout << result;

	return 0;
}