[BOJ] A → B (16953)

www.acmicpc.net/problem/16953

16953번: A → B

난이도 - 실버 1

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

 

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int A, B;
int main() {
    cin >> A >> B;


    queue<vector<long long>> q;
    int ans = -1;
       q.push({ A, 1 });
    while (!q.empty()) {
        long long x = q.front()[0], cnt = q.front()[1];
        if (x == B) {
            ans = cnt; break;
        }
        q.pop();
        cnt++;
        if (x * 2 <= B) {
            q.push({ x * 2, cnt });
        }
        if (x * 10 + 1 <= B) {
            q.push({ x * 10 + 1, cnt });
        }
    }
    cout << ans;
    return 0;
}

풀이

단순한 BFS, DFS 풀이다.

단 최소 연산을 구하는 것에는 BFS가 더 빠른 연산을 낼 수 있다.

 

1. 만들 수 없는 경우에는 -1을 출력해야 하므로 ans의 기본값은 -1로 설정한다.

2. 초기 값인 A와 1(마지막에 1을 더해주는 대신 1을 넣는다.

3. BFS 작업을 한다. 여기서 주의 할 점은 10^9은 10억인데 10억의 맨 뒤에 1을 붙이면 100억이 되기 때문에 int로 표현 못하는 경우가 생기므로 x(계산한 식)를 long long 형으로 지정한다.

4. 만약 x*2, x*10+1(마지막에 1을 추가한 수) 가 B보다 크면 큐에 넣지 않고 작으면 넣는다.

5. BFS를 하다가 x==B이면 ans를 cnt로 설정하고 출력 후 종료