[C++][백준 16953] A → B

[문제]

16953번: A → B (acmicpc.net)

16953번: A → B

[문제 풀이]

bfs를 이용해 2배로 값이 퍼지는 것과 10배 + 1을 더한 값의 2가지 루트로 계속 뻗어나가게 만들어주자.

* 주의사항 : 범위가 int 값을 넘어설수 있으니 long long을 이용하자.

* 주의사항 : 계속해서 넣게 된다면 해결해야 하는 부분이 너무 많아지고 long long 값을 넘어서거나 혹은 queue에 너무나도 많은 데이터가 들어가 메모리 초과가 일어날 수 있다.

나는 처음에 2개의 경우를 계속 넣고 a가 b로 변하는 최대의 범위를 구한뒤에 해당 범위를 벗어날 경우에 반복문을 그만두게 만들었는데 이렇게 만들면 최악의 경우에 너무나도 많은 데이터가 들어가 메모리 초과가 발생한다.

 

pair를 이용해 현재의 값과 현재 몇번이 일어났는지 저장을 해주기만 하면 나머지는 주의사항만 보고 풀 수 있을정도로 간단한 문제이다.

[코드]

#include<iostream>
#include<queue>

using namespace std; 

void dfs(int a, int b){
    queue<pair<long long, int> > prime;
    prime.push(make_pair(a,1));

    while(prime.size()>0){
        if(prime.front().first == b){
            break;
        }

        if(prime.front().first * 2 <= b){
            prime.push(make_pair(prime.front().first * 2 , prime.front().second + 1));
        }

        if(prime.front().first * 10 + 1<= b){
            prime.push(make_pair(prime.front().first * 10 + 1 , prime.front().second + 1));
        }

        prime.pop();
    }

    if(prime.size() <= 0){
        cout<<-1<<endl;
        return;
    }

    cout<<prime.front().second<<endl;

    return;
}

int main(){
    int a,b;
    cin>>a>>b;
    dfs(a,b);
    return 0;
}