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

 

<DFS 코드>

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

int mini = 10000; // 임의의 큰수
long long A, B, cnt;

void dfs(long long a, int cnt)
{
	if (a > B) return;

	if (a == B)
	{
		mini = min(mini, cnt);
	}
	dfs(a * 2, cnt + 1);
	dfs(a * 10 + 1, cnt + 1);

}

int main()
{
	cin >> A >> B;

	dfs(A, 1);
	
	if (mini == 10000) cout << -1;
	else cout << mini;
}

 

<거꾸로 탐색하는 코드>

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

int A, B, cnt;

int main()
{
	cin >> A >> B;

	while (true)
	{
		if (A > B)
		{
			cout << -1;
			break;
		}
		if (A == B)
		{
			cnt++;
			cout << cnt;
			break;
		}

		if (B % 10 == 1)
		{
			B--;
			B /= 10;
		}
		else if (B % 2 == 0)
		{
			B /= 2;
		}
		else
		{
			cout << -1;
			break;
		}

		cnt++;
	}
	
}

 

풀이 방법

dfs 구현을 어떻게 해야할지... 큐를 만들어서 풀어야할지 고민을 많이 했던 문제이다. 어차피 A에 2를 곱하거나 1을 오른쪽에 붙이거나 둘중 하나이므로 거꾸로 답부터 탐색을 해서 답을 찾았고 DFS코드의 경우 다른 분의 숏코드를 참고하였다.(www.acmicpc.net/source/21103705)

 

 

 

www.acmicpc.net/problem/16953

16953번: A → B