[백준 16953] A->B

A → B

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	3052	1373	1071	43.185%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

xxxxxxxxxx
2 162

예제 출력 1 복사

xxxxxxxxxx
5

2 → 4 → 8 → 81 → 162

예제 입력 2 복사

xxxxxxxxxx
4 42

예제 출력 2 복사

xxxxxxxxxx
-1

예제 입력 3 복사

xxxxxxxxxx
100 40021

예제 출력 3 복사

xxxxxxxxxx
5

 

풀이

큐를 이용해서 풀었습니다.

 

int자료형을 사용하면 오버플로가 발생하니 long으로 해주는것을 신경써주셔야 합니다.

 

 

 

코드

import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
    static int t,n;
    static int arr[];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        
        long a = Long.parseLong(t[0]);
        long b = Long.parseLong(t[1]);
        
        
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(a,0));
        while(!q.isEmpty()) {
            Node c = q.poll();
            if(c.num==b) {
                System.out.println(c.cnt+1);
                return ;
            }
            long first = c.num*10+1;
            long second = c.num*2;
            if(first<=b) {
                q.add(new Node(first,c.cnt+1));
            }
            if(second<=b) {
                q.add(new Node(second,c.cnt+1));
            }
        }
        System.out.println(-1);
        
    }
}
class Node{
    long num;
    int cnt;
    Node(long num, int cnt){
        this.num = num;
        this.cnt=cnt;
    }
}