[백준] 16953 - A → B

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

16953번: A → B

 

A를 2배 혹은 오른쪽 끝에 1을 추가해 B를 찾는 간단한 문제입니다. 저는 queue에 계산중인 수와 계산 횟수를 저장해 bfs로 진행하였습니다. 이러면 빠지는 경우의 수 없이 2^n 만큼 전부 다 훑어볼 수 있습니다.

 

#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;

queue<pair<ll, int>> q;
ll a, b;

void bfs() {
    q.push({a, 1});

    while (!q.empty()) {
        ll x = q.front().first;
        int y = q.front().second;
        q.pop();

        if (x > b) {
            continue;
        } else if (x == b) {
            cout << y << "\n";
            return;
        } else {
            if (2 * x <= b)
                q.push({2 * x, y + 1});
            if (10 * x + 1 <= b)
                q.push({10 * x + 1, y + 1});
        }
    }

    cout << "-1\n";
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> a >> b;

    bfs();
    return 0;
}

 

하지만 문제 알고리즘 분류에 그리디가 있었고 좀 더 간단하게 풀 수 있을 것 같아 찾아보던 도중 좀 더 간략하고 명쾌한 답변을 찾을 수 있었습니다. 계산은 총 1) 2배로 만들거나 2) 10배 후 1을 추가하는 2가지 경우가 있습니다. 하지만 2번 계산이 훨씬 수를 크게 할 수 있다는 것을 알 수 있습니다. 그렇기에 B를 직접 건드려 홀수면 10을 나누고 이외에는 2를 나누는 식으로 좀 더 그리디한 방식으로 해결하는 코드입니다. 계산을 직접하는 A를 건드린 게 아닌 B를 건드린 다는 역발상도 필요해 보입니다.

https://ideone.com/SWFugI

Ideone.com

#include <iostream>
using namespace std;
 
int main(){
    long long a,b; cin>>a>>b; int count=0;
    while(a!=b){
        if(b==0) {cout<<"-1"; return 0;}
        if(b%2==1) b/=10;
        else b/=2; count++;
    } cout<<count+1;
}