[백준 16953] A → B

🔗 알고리즘 문제

간단한 BFS로 해결할 수 있었던 문제

문제 분석

정수 A와 B가 주어질 때 A를 B로 만들기 위한 연산의 갯수를 출력하는 문제이다.

이 때 할 수 있는 연산은 현재 값에 2를 곱하는 것과 현재 값에 10을 곱한 후 1을 더하는 것 2가지이다.

A: 2
B: 162

2 → 4 → 8 → 81 → 162	// 5번

발상 & 알고리즘 설계

DP로 해결할가 하였지만 BFS로도 해결할 수 있을 것 같아서 BFS로 해결하였다.

길이 항상 두 개인 BFS라고 생각하면 쉽게 해결할 수 있다.

수는 항상 증가하므로 굳이 방문체크를 해주지 않아도 되고 목표 값보다 클 때만 예외처리를 해주었다.

코드

#include<iostream>
#include<queue>

using namespace std;

int main(){
    long long a;
    long long b;

    queue<pair<long long, long long>> q;

    cin >> a >> b;

    q.emplace(a, 1);

    while(!q.empty()){
        pair<long long, long long> cur = q.front();
        q.pop();

        if(cur.first == b){
            cout << cur.second;
            return 0;
        }

        if(cur.first > b){
            continue;
        }

        long long next = cur.first * 2;
        if(next <= b)
            q.emplace(next, cur.second + 1);

        next = cur.first * 10 + 1;
        if(next <= b)
            q.emplace(next, cur.second + 1);
    }

    cout << -1;
}