[백준 16953번 / C++] A → B

dfs 문제이다 

 

#접근방법 

현재 값 current 변수에서

 

1. 곱하기 2를 해서 dfs를 호출. 

2. 곱하기 10을 한 후 +1 을 dfs로 호출 

 

이 두가지 경우를 dfs 함수 안에 두고 current 값이 B와 동일하다면  cnt값이 큰 것을 고른다. 

 

즉, 위의 조건에서 1번을 통해 B값을 도출할 수 있고 2번을 통해 B값을 도출할 수 있으니 

재귀호출한 횟수를 세어주는 cnt값을 비교해서 작은 값을 answer값에 저장시켜준다. 

 

#include <iostream>
#include <algorithm> 
using namespace std; 
long long a, b; 
long long answer = 987654321; 
void dfs(long long cur, long long cnt) {
	if (cur == b) {
		answer = min(answer, cnt); 
		return; 
	}
	if (cur > b) {
		return; 
	}
	dfs(cur * 2, cnt + 1);
	dfs(cur * 10 + 1,cnt + 1);
	return; 
}

int main() {
	cin >> a >> b; 
	dfs(a,1); 
	if (answer == 987654321)cout << -1;
	else cout << answer; 	
}

 

16953번: A → B