문제

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

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

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

입력

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

출력

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

답안제출

import java.util.Queue;
import java.util.LinkedList;
import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static long start, end;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Long.parseLong(st.nextToken());
        end = Long.parseLong(st.nextToken());
        System.out.println(BFS(1));

    }
    public static int BFS(int cnt) {
        Queue<Long> q = new LinkedList<>();
        q.add(start);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                long n = q.poll();
                if (n == end) {
                    return cnt;
                }
                if (n * 2 <= end) {
                    q.add(n * 2);
                }
                if (n * 10 + 1 <= end) {
                    q.add(n * 10 + 1);
                }
            }
            cnt++;
        }
        return -1;
    }
}

• 계속되는 메모리초과로 문제다시 검토.
• int 형을 모두 long형으로 대체. -> n x 10+1 또는 n x 2부분이 int범위를 벗어나기 때문.