C++ / 백준 / 16953 / A → B

문제

 

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

16953번: A → B

문제풀이

 

이런 문제는 B를 A로 만드는 과정을 탐색하는 게 더 쉬운 것 같다.

B를 A로 만드는 과정 중 할 수 있는 것은 두 가지이다.

B가 짝수 일 때 2로 나누는 것, B의 일의 자리숫자가 1일 때 1을 없애는 것.

이 이외의 경우는 B를 A로 만들 수 없는 경우이므로 -1을 출력하면 된다.

 

반복문을 돌려 B가 A가 될 때까지 반복을 한다.

B를 10으로 나눈 나머지가 1이면 B를 10으로 나누고,

B가 짝수이면 B를 2로 나눈다.

B가 A보다 작게되면 만들 수 없으므로 -1을, 위의 두 가지 행동을 할 수 없으면 -1을 출력하면 된다.

 

코드

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int A(0), B(0), answer(1);
	cin >> A >> B;

	while (B != A) {
		if (B < A) {
			answer = -1;
			break;
		}
		else if (B % 10 == 1) {
			B /= 10;
		}
		else if (B % 2 == 0) {
			B /= 2;
		}
		else {
			answer = -1;
			break;
		}
		++answer;
	}
	cout << answer;
}