(BoJ) 16953 A → B C++

by

개요

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

16953호: A → B

'추천 관련글,

첫 번째 줄은 A와 B를 제공합니다(1 ≤ A < B ≤ 109).

www.acmicpc.net

Silver 2 검색 질문입니다.

설명하다

두 가지 옵션이 있습니다. 2를 곱하고 맨 오른쪽에 1을 더합니다.

어떤 옵션이 먼저인지 알 수 없기 때문에 모든 경우를 집계하기로 결정했습니다.

그래서 저는 BFS를 사용했습니다.

BFS는 n*10+1 및 n*2를 대기열에 넣습니다.

n의 int가 넘쳤기 때문에 한 번 틀렸습니다.

롱롱으로 해결했습니다.

코드

#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;
}