[BOJ] 16953 A → B C++

개요

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

16953번: A → B

실버2 난이도 문제다.

풀이

2를 곱하기, 1을 가장 오른쪽에 추가하기 두 가지의 선택지가 있다.

어느 선택지가 먼저일지 알 수 없으므로 모든 경우의 수를 따져봐야 한다고 판단했다.

그래서 BFS를 사용했다.

n * 10 + 1과 n *2를 큐에 넣으며 BFS 하면 된다.

 

n의 int형 overflow 때문에 한 번 틀렸다.

long long으로 해결했다.

코드

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

struct Node
{
	long long n;
	int cnt;
};
long long A, B;
int ans = -1;

void BFS()
{
	queue<Node> q;
	q.push({ A, 1 });

	while (!q.empty())
	{
		auto [n, cnt] = q.front();
		q.pop();

		if (n == B)
		{
			ans = cnt;
			return;
		}

		long long nn;
		nn = n * 2;
		if (nn <= B)
				q.push({ nn, cnt + 1 });

		nn = n * 10 + 1;
		if (nn <= B)
				q.push({ nn, cnt + 1 });
	}
}

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

	BFS();

	cout << ans;
}