[백준] 16953번 A -> B

문제: 16953번: A → B

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int a, b;
    cin >> a >> b;
    // 정수 a를 b로 바꾸는데 필요한 연산의 최솟값을 구한다?
    // b를 a로 바꾸는 연산의 개수를 구하면 됨!!

    int cnt = 0;
    bool flag = false;
    while (a < b) {
        if (b % 2 == 0)
            b /= 2;
        else if (b % 10 == 1)
            b /= 10;
        else {
            break; // 이 경우는 가능한 연산에 속하지 않으므로 그냥 a 를 b 로 못 만들어. 걍 나가
        }

        cnt++;
         
        if (a == b) {
            flag = true;
            break;
        }
    }

    if (flag)
        cout << cnt + 1 << "\n";
    else
        cout << -1 << "\n";


    return 0;
}

 

이 문제는 BFS 로도 풀 수 있는 문제라고 하는데 나는 그리디 방법밖에 생각나지 않아서 그냥 그리디로 풀었다.

 

일단 이 문제는 입력으로 주어진 a 와 b 가 있다고 할 때, 가능한 연산만을 사용해서 a 를 b 로 만드는 최소 연산의 수를 구하는 문제이다. 

 

a 를 b 로 만든다고 생각하면 매 단계마다 분기가 2개로 나뉘니까 쉽지 않다. a 를 b 로 만든다고 생각하면 이 문제를 해결할 수 없다. 

 

그렇다면 이 문제를 해결할 수 있는 방법은 무엇이냐? 이는 바로 b 를 a 로 만드는 것이다. b 를 a 로 만들 수 있는 방법은 1가지 밖에 없다. 즉, 매 단계마다 사용 가능한 연산의 종류가 정해져 있기 때문에 분기가 나뉘지 않는다. 

 

즉, 매 단계마다 b 의 값을 조정해주면서 이 값이 최종적으로 a 값과 같아지는지를 판단하면 쉽게 해결할 수 있는 문제이다. 

 

근데 유의해야 할 점은 문제상에서 주어진 것처럼 이용 가능한 연산의 종류는 2가지라는 것이다. 2를 곱하는 것과, 숫자의 맨 오른쪽 끝에 1을 붙이는 것. 

 

처음에는 경우를 if, else 이런식으로 해서 맨 오른쪽 끝이 1일 때 10으로 나눠야 하는데, 그렇지 않은 경우에도 10으로 나눠버려서 틀렸다. 즉, if, else if, else 이렇게 경우를 나눠야 문제를 제대로 해결할 수 있었다. else 인 경우에는 사용 가능한 연산이 아니라는 것을 의미하므로 a 가 b 가 될 수 없음을 의미한다. 즉, 이 경우에는 그냥 break 으로 빠져나가서 -1 을 출력해주면 된다.

 

옛날에 한 번 풀었던 문제인 것 같은데 아직까지 문제 풀이 접근 방식을 안 잊고 기억하고 있는게 살짝 뿌듯했다. 앞으로도 잊지 말고 잘 기억해놓아야겠다. ^0^

 

 

 

참고자료:

[DFS/BFS/완전탐색] ▲ 16953번 - A → B(BFS) — mumu 개발 블로그

[DFS/BFS/완전탐색] ▲ 16953번 - A → B(BFS)

이거는 BFS 로 푸는 방법인데 확실히 그냥 그리디로 푸는게 훨씬 간단한 것 같다. 뭐 그래도 알아두면 좋으니까~_~