알고리즘&자료구조/문제
[BOJ] 16953 A → B C++
Nakuri
2023. 2. 20. 04:17
개요
https://www.acmicpc.net/problem/16953
16953번: A → B
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
www.acmicpc.net
실버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;
}
728x90