A → B

16953번: A → B
https://www.acmicpc.net/problem/16953

문제

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

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

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

입력

첫째 줄에 A, B ($1$ ≤ A < B ≤ $10^9$)가 주어진다.

출력

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

예제 입출력

// 입력 1			// 출력 1
2 162				5

2 → 4 → 8 → 81 → 162


// 입력 2			// 출력 2
4 42				-1

해결 방향

위와 같은 트리를 너비 우선 탐색한다.
Pair 클래스를 사용하여 depth를 기록한다.

코드

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

int main() {
    long long int A, B, x, y;
    int cnt;
    bool v = false;
    cin >> A >> B;

	// BFS를 위한 큐를 선언한다. 
    // 정수와 연산 횟수를 동시에 기록하기 위하여 pair 클래스를 사용한다.
    queue<pair<long long int,long long int>> q;
    
    // 정수 A를 큐에 넣는다.
    q.push(make_pair(A, 0));

	// 큐가 빌 때까지 반복한다. 
    while(!q.empty()) {
    	
        // 큐의 front값으로 초기화한다.
        A = q.front().first; 
        cnt = q.front().second;
        
        // 방문한 정수를 삭제한다. 
        q.pop();
        
        // 연산한 값과 B가 같다면 반복문을 종료한다.
        if(A==B) {
            v = true;
            break;
        }
        /* 연산한 값이 B보다 작다면, 또 다시 연산한 두 정수를 큐에 넣는다.
		   연산 횟수는 부모의 횟수보다 1 증가한다. */ 
        else if(A<B) {
            x = A*2;
            y = A*10+1;

            q.push(make_pair(x,cnt+1));
            q.push(make_pair(y,cnt+1));
        }
    }

	// 연산의 최솟값에 1을 더한 값을 출력한다.
    if(v) cout << cnt+1;
    // B를 만들 수 없는 경우에는 -1을 출력한다.
    else cout << -1;
}

메모리 : 2416 KB
시간 : 0 ms