[백준] 16953번 A → B C++ 코드

코드

#include <iostream>

using namespace std;
typedef long long ll;
const ll INF = 987654321;
ll a,b,res = INF;
// 2를 곱한다
// 1을 수의 가장 오른쪽에 추가한다

void go(string x, ll cnt) {
	ll tmp = stol(x);
	if(tmp > b) return;
	if(tmp == b) {
		res = min(res, cnt);
		return;
	}
	// 2 곱한 거
	go(to_string(tmp*2) ,cnt + 1);
	// 1더한 거
	go(x + "1", cnt + 1);
	return;
}

int main() {
	cin >> a >> b;
	go(to_string(a), 0);
	cout << (res == INF ? -1 : (res + 1)) << '\n';
	return 0;
}

풀이

문제를 해결하고 나서 태그를 확인하니까 BFS, 그리디로 해결할 수도 있는 문제였다. 우선 위 풀이는, 1을 더해주거나 2를 곱하면서 수를 찾아나가는 과정을 재귀로 해결한 코드이다. 수가 빠르게 증가하기 때문에 재귀의 깊이가 깊어질 것이라 생각하지 않아서 이렇게 접근했다. 

 

그리디 풀이의 경우 B -> A로 가는 방법을 생각하면 된다. 뒤에 1이 있다면 1을 떼고, 짝수라면 2로 나눠주고, 두 조건을 만족하지 않는다면 -1을 출력한다.

 

BFS 풀이의 경우는 처음 x를 큐에 넣고 x*2, 10*x + 1이 b보다 작거나 같을 때 큐에 삽입하면서 탐색하면 된다.

 

여러 풀이가 나와서 재밌었던 문제였다.