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

오늘은 백준16953번 A -> B 문제를 풀어보도록 하자.

고민을 좀 했던 문제다. 친구의 아이디어로 __역산__이라는 아이디어를 얻었다. BFS로도 풀 수 있다 ! 시간 복잡도는 크게 차이 안난다.

접근법에서 아이디어를 알아봅시다 :)

문제는 다음과 같다.

                               [접근법]

  1. 처음 값이 아닌 도달 값에서 처음 값으로 될 수 있나를 판단하면 됩니다.
  
  2. 만일 도달 값이 짝수면 2를 나누어주고, 끝자리가 1이면 1을 빼고 10을 나누어 주는 것을 반복합니다. 
  
  3. 도달했으면 cnt 값을 출력 ! 만일 도달 값이 처음 값보다 작다면 -1을 출력합니다. 왜냐면 더 이상 연산이 불가능하기 때문입니다.

                                     [코드]
#include <iostream>
using namespace std;

int main() {
	int A, B, cnt = 1;

	cin >> A >> B;

	while (1) {
		if (A == B) {
			cout << cnt << '\n';
			return 0;
		}
		else if (A > B) {
			cout << -1 << '\n';
			return 0;
		}
		cnt++;
		if (B % 2 == 0) {
			B /= 2;
		}
		else {
			if (B % 10 == 1) {
				B = (B - 1) / 10;
			}
			else {
				cout << -1 << '\n';
				return 0;
			}
		}
	}
}