백준 16953 (A -> B)

jh Seo·2025년 8월 17일
0

백준

목록 보기
196/201

개요

A -> B

문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

2를 곱한다.
1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

접근 방식

  1. 만약 2를 곱하거나 1을 더하는 문제라면 B에서 시작해서
    홀수라면 -1, 짝수라면 /2해가면서 풀 수 있지만 이건 끝에 1을 넣는 문제다.

  2. dp로 *2 와 *10 +1 과 같은 모든 경우를 넣으며 풀기엔 범위가 10억이라 힘들다.

  3. 따라서 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;
	
}
profile
코딩 창고!

0개의 댓글