백준 16953번 A->B

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

16953번: A → B

 

 

 

 

 

<접근방법>

A에서 B로 가야합니다.

dfs, bfs 탐색으로 중복을 제거해가며 탐색하기에는 시간이나 메모리가 부족합니다.

다른 방법이 필요합니다.

 

역으로 생각해봅시다.

B에서 A로 가봅시다.

A 에서 B로 올라가는 규칙에 의해서 중간 과정에 있는 수는 무조건 짝수이거나

마지막 자리수가 1인 수 밖에 없습니다.

 

그러므로 위 조건을 충족하면서 가다가 A가 되면 성공인 것이고

안되면 실패인 것이죠.

 

 

 

 

<느낀 점>

거꾸로 생각하기

 

 

---

 

 

 

<코드>

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

int a, b;

int main() {
	cin >> a >> b;

	int cnt = 0;
	while (1) {
		if (a > b) {
			cout << -1 << '\n';
			break;
		}
		if (a == b) {
			cout << cnt + 1 << '\n';
			break;
		}

		if (b % 10 == 1) {
			b /= 10;
		}
		else if(b % 2 == 0){
			b /= 2;
		}
		else {
			cout << -1 << '\n';
			break;
		}
		cnt++;
	}
	return 0;
}