[ BOJ ][JAVA][16953] A -> B

https://www.acmicpc.net/problem/16953

16953번: A → B

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	11683	4998	3983	40.998%

문제

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

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

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

입력

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

출력

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

예제 입력 1

2 162

예제 출력 1

5

2 → 4 → 8 → 81 → 162

예제 입력 2

4 42

예제 출력 2

-1

예제 입력 3

100 40021

예제 출력 3

5

접근

증가하는 경우의 수를 차례로 접근하므로 bfs로 구현하였다.

코드

/**
 * BOJ 16953 A -> B 
 * Greedy, BFS or DP
 */
import java.io.*;
import java.util.*;

public class p16953 {
    static class Node {
        long num, cnt;
        public Node(long num, long cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }
    static int a, b;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        bfs(a, b);
    }
    static void bfs(int num, int target) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(num, 0));

        while (!q.isEmpty()) {
            Node cur = q.poll();
            if (cur.num == target) {
                System.out.println(cur.cnt + 1);
                return;
            }
            if (cur.num > target) continue;
            q.add(new Node(cur.num * 2, cur.cnt + 1));
            q.add(new Node(cur.num * 10 + 1, cur.cnt + 1));
            //q.add(new Node((cur.num * 2) * 10 + 1, cur.cnt + 1));
            //q.add(new Node((cur.num * 10 + 1) * 2, cur.cnt + 1));
        }
        System.out.println("-1");
    }
}