[백준 16953] A → B

문제

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

16953번: A → B

 

 

문제 분석 

A에 2를 곱하거나, 1을 가장 오른쪽에 추가하여 수 B를 만드는 간단한 문제이다. 

 

 

알고리즘 설계

입력을 받고 queue에 넣어 queue가 비어있지 않을때 작동되는 반복문을 만든다. 

 

queue앞에 있는 수에 2을 곱하거나 맨오른쪽에 1을 두는 코드를 만들고 B를 넘었다면 queue에 넣어주지 않는다. 

 

만약 B에 도달했다면 얼마만에 도착 했는지 출력하고, 도착하지 못 하였다면 -1을 출력한다. 

 

 

유의점

입력되는 값이 십억단위까지 올라가기에 int가 아닌 long long을 사용한다. 

 

vector대신 map을 사용하여 추가에 문제가 없도록 해준다. 

 

 

코드

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

int main()
{
    long long input1, input2;
    cin >> input1 >> input2;
    unordered_map<long long, int> um;
    queue<long long> q;

    q.push(input1);
    um[input1] = 1;

    while (!q.empty())
    {
        long long front = q.front();
        q.pop();

        if (front * 2 <= input2 && um[front * 2] == 0)
        {
            um[front * 2] = um[front] + 1;
            q.push(front * 2);
        }
        if (front * 10 + 1 <= input2 && um[front * 10 + 1] == 0)
        {
            um[front * 10 + 1] = um[front] + 1;
            q.push(front * 10 + 1);
        }
        if (front == input2)
            break;
    }

    if (um[input2] == 0)
        cout << -1;
    else
        cout << um[input2];
}