문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
2를 곱한다.
1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
만약 2를 곱하거나 1을 더하는 문제라면 B에서 시작해서
홀수라면 -1, 짝수라면 /2해가면서 풀 수 있지만 이건 끝에 1을 넣는 문제다.
dp로 *2 와 *10 +1 과 같은 모든 경우를 넣으며 풀기엔 범위가 10억이라 힘들다.
따라서 BFS를 이용해 *2 와 *10 +1해보며 최단 경로를 측정하는 식으로 풀었다.
#include <string>
#include <vector>
#include<queue>
#include<iostream>
#include<cmath>
using namespace std;
/// <summary>
/// start에서 end까지 진행하며 end에 도달했을 때 최단경로
/// </summary>
/// <param name="Start"></param>
/// <param name="End"></param>
/// <param name="curNum"></param>
/// <returns></returns>
int BFS(int Start,int End)
{
queue<long long> q;
q.push(Start);
int answer = 0;
while (!q.empty())
{
int levelSize = q.size();
//각 레벨 진행시 answer++
answer++;
for (int i = 0; i < levelSize; i++)
{
long long curNode = q.front();
q.pop();
//*2값과
if(curNode*2 < End)
q.push(curNode * 2);
//10곱하고 +1한 값 넣기
if(curNode*10+1 < End)
q.push(curNode * 10 + 1);
if (curNode * 2 == End || curNode * 10 + 1 == End)
return answer;
}
}
return -1;
}
int main()
{
int A, B;
cin >> A >> B;
int Answer =BFS(A, B);
Answer = Answer == -1 ? -1 : Answer + 1;
cout<<Answer;
}