[백준OJ] 16953번 A->B

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

16953번: A → B

---

 

-풀이-

 

dfs를 이용하여 모든 경우를 탐색하며, a==b일경우가 되면 , cnt값을 갱신했다.

 

-코드-

#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;

long long answer = LLONG_MAX;

void dfs(long long a,long long b,long long cnt) {
	if (a == b) {
		answer = min(answer, cnt);
		return;
	}
	else if (a > b) {
		return;
	}
	else {
		dfs(a * 2, b, cnt + 1);
		dfs(a * 10 + 1, b, cnt + 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	long long a, b;
	cin >> a >> b;
	dfs(a, b,1);
	if (answer == LLONG_MAX) answer = -1;
	cout << answer << "\n";
	return 0;
}