[백준 / BOJ] 16953번 : A => B (C++)

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

16953번: A → B

 이번 문제는 2가지 연산만으로 A를 B로 바꾸는데 필요한 최소 연산 횟수를 구하는 문제입니다. 만약 불가능하다면 -1을 출력합니다. 이 문제는 BFS로도 풀 수 있지만 저는 그리디 알고리즘으로 풀었습니다. 

 

우선 가능한 연산 두 가지는 다음과 같습니다.

• 2를 곱한다.
• 1을 수의 제일 오른쪽에 추가한다 (ex : 3 -> 31)

 위의 조건으로 인해 연산을 하는 중간에는 수가 짝수이거나, 일의 자리 수가 1인 두 가지 조건을 반드시 만족합니다. 그러므로 B에서 2를 나누거나, 오른쪽 1을 삭제하는 두 가지 연산을 하는 방법으로 A를 구하는 방법과 같습니다. 연산 중간에 1이 아닌 홀수가 나온다면 답을 만들 수 없습니다.

 

아래는 제 코드입니다. 

 

#include <iostream>

using namespace std;
using ll = long long;

int a, b;
int cnt = 0;

int main() {
    /*ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);*/
    cin >> a >> b;
    while (a < b) {
        if (b % 2 == 0) {
            b /= 2;
            cnt++;
        }
        else if (b % 10 == 1) {
            b /= 10;
            cnt++;
        }
        else
            break;
    }

    cout << ((a == b) ? (cnt + 1) : (-1)) << endl;

    return 0;
}