[백준] #16953 A → B

16953번: A → B (acmicpc.net)

16953번: A → B

백준 #12904 A와 B와 상당히 유사한 문제이다. 다른점이라고 한다면, data-type이 string이 아닌 int 라는 점..?

알고리즘 분류는 그래프와 BFS로 되어있던데, 굳이 BFS를 활용하지 않아도 충분히 풀 수 있다.

---

• 풀이

B에서 A를 만드는 알고리즘으로 바꾸어 생각해보자.

그렇다면 적용할 수 있는 연산은 B에 따라 총 3가지로 정해지게 된다.

case 1. B의 마지막 숫자가 1인 경우 : 10으로 나누어 줌 (마지막 숫자인 1을 없애주는 효과)
case 2. B가 짝수인 경우 : 2로 나누어 줌
case 3. B의 마지막 숫자가 1이 아닌 홀수인 경우 : A에 어떤 수가 와도 만들어질 수 없는 경우 이므로, break로 반복문 탈출

B가 A보다 작아질 경우, 반복문을 탈출하고 적절히 출력

B에 따라 명확한 규칙성이 생기기 때문에 훨씬 더 쉽게 구현할 수 있다.

---

• 구현

#include <iostream>

using namespace std;

int main() {
    long long A, B, cnt = 0;
    cin >> A >> B;

    bool flag = false;

    while(B >= A) {
        if (A == B) {
            flag = true;
            break;
        }
        if (B%10 == 1) {
            B /= 10;
            cnt++;
        }
        else if (B%2 == 0) {
            B /= 2;
            cnt++;
        }
        else break;
    }
    flag ? cout << cnt+1 : cout << -1;

    return 0;
}

---

case 3의 경우를 고려하지 않아서 두번 정도 틀렸다.

입력의 worst-case가 10억 밖에 안되기에 data-type은 int든, long long이든 상관없는 듯 했다.