[백준 16953] A → B [C/C++]

백준 - 16953

---

풀이

Queue에 연산값과 최솟값을 저장해주어, 연산값이 B가 될 때까지 탐색해주는 방식으로 풀이했다.

처음으로 들어오는 값이 1e8일 경우 10을 곱해주면 int의 범위를 벗어나므로 num은 long long으로 담아주었다.

만약 연산이 불가능하다면, num == B 조건을 만족하지 못하고 모든 Queue가 비었다는 것이므로, -1을 출력하면 된다.

---

소스코드

#include <stdio.h>
#include <queue>
using namespace std;
void bfs(int A, int B){
    queue<pair<int, int> > q;
    q.push(make_pair(A, 1));

    while (!q.empty()){
        long long num = q.front().first;
        int cnt = q.front().second;
        q.pop();

        if (num == B){
            printf("%d", cnt);
            return;
        }
		
        if (num*2 <= B) q.push(make_pair(num*2, cnt+1));
        if (num*10 +1 <= B) q.push(make_pair(num*10 +1, cnt+1));
    }
    printf("-1");
}
int main(){
    int A, B;
    scanf("%d %d", &A, &B);
    bfs(A, B);
}

---

출처

16953번: A → B