백준 16953문제. A→B

A→B

 

---

Problem?

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

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

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

 

Input

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

 

Output

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

 

Solution

규칙 찾기

최종 값에 +1을 해야하므로 -2로 나오게 했다.

 

가정 n, m : input cnt : count

 

 

Code

#include	<iostream>

using namespace std;

int main() {
	long long int n, m;
	int cnt = 0;

	cin >> n >> m;

	while (1) {
		if (n == m) {
			break;
		}

		if (m % 10 == 1) {
			m = m / 10;
			cnt++;
		}
		else if (m % 2 == 0) {
			m = m / 2;
			cnt++;
		}
		else {
			cnt = -2;
			break;
		}

		if (m < n) {
			cnt = -2;
			break;
		}
	}
	cnt++;

	cout << cnt << "\n";

	return 0;
}

 

---

규칙문제.

 

쉬웠던 문제