백준 16953번, A -> B

백준 16953번 c++ 문제풀이

문제:

백준 16953

1번 풀이:

1. A, B를 입력받는다.
2. B에서부터 거꾸로 진행한다.
3. B를 2로 나누는 과정, 카운트 증가시킴
4. B를 10으로 나눈 나머지가 1임을 확인하는 과정, 카운트 증가시킴
5. 위의 과정을 통해 B값을 업데이트 해준다.
6. 만약 위 과정을 진행하는데, 업데이트 된 B의 값이 A의 값보다 작다면 -1,
7. B의 값이 15와 같이 2로도 안나눠지고 끝자리가 1이 아닌 경울 -1, 출력
8. 예외가 아닌 경우 count +1 값을 출력한다.

코드:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){

    int a, b;
    int count = 0;

    cin >> a >> b;

    while(a!=b){
        if(a > b){
            cout << -1;
            return 0;
        }
        if(b % 10 == 1){
            b = b/10;
        }else if(b%2 == 0){
            b = b/2;
        }else{
            cout << -1;
            return 0;
        }
        count++;
    }

    cout << count+1;
    return 0;
}

2번 풀이:

1. bfs 즉 너비 우선 탐색을 적용한다.
2. 큐에 a의 값과, count 값인 1을 push한다.
3. 큐의 맨앞에 있는 값을 pop하고 그 값을 업데이트 했을 때의 값이 b보다 작거나 같은 값이 있으면 큐에 push하고 아니면 하지 않는다.
4. 큐가 empty가 될 때까지 b를 만들지 못하였다면 -1출력, 그 전에 찾았다면 count값을 출력한다.
5. 여기서는 자료형이 1ong long 인게 중요했다.

코드:

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

long long a, b;

void bfs(){
    queue<pair<long long, long long>> q;

    q.push({a, 1});

    while(!q.empty()){
        long long up;
        int count;

        up = q.front().first;
        count = q.front().second;
        q.pop();
        if(up == b){
            cout << count ;
            return ;
        }else{
            if(up * 2 <= b){
                q.push({up * 2, count +1});
            }
            if(up*10+1 <= b){
                q.push({up * 10 + 1, count +1});
            }
        }
    }
    cout << -1;
}

int main(){

    cin >> a >> b;

    bfs();
    return 0;
}

감사합니다.