[BOJ 16953 // C++] A → B

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16953번 문제인 A → B이다.
문제는 아래 링크를 확인하자.

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

16953번: A → B

주어진 정수의 끝에 1을 붙이는 것은 주어진 정수에 10을 곱하고 1을 더한 것과 같다는 점을 떠올린다면, 수에 가할 수 있는 조작 두 가지 모두 수가 지수적으로 증가하므로 bfs를 통해 시간 내로 문제를 간단히 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;

ll E;
queue<pair<ll, int>> que;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll temp; cin >> temp >> E;
	que.push({ temp,1 });

	while (!que.empty()) {
		ll current = que.front().first;
		int idx = que.front().second;
		que.pop();

		if (current == E) {
			cout << idx;
			return 0;
		}

		if (2 * current <= 1000000000) que.push({ 2 * current,idx + 1 });
		if (10 * current + 1 <= 1000000000) que.push({ 10 * current + 1,idx + 1 });
	}

	cout << -1;
}