백준 16953번 메모리 초과 및 시간 초과(java)

이 문제는 처음에 BFS로 접근하였다.
또한 받는 변수들이 10의 9승보다 작거나 같아서 int로 선언하였다.
하지만 메모리 초과가 발생하였다.

그 이유는 당연하다 2를 곱하거나 10을 곱하는 연산이 있기 때문에 오버플로우가 발생한다. 그래서 long으로 바꿔주니 이제는 시간초과가 발생한다.

이 방법이 효율적인 방법이 아니다.
따라서 다른 방법을 생각해보니 그리디 알고리즘을 통해서 B에서 A로 갈 수 있는가를 판단하는 방법을 고안했다.

B에서 A로 가려면 일단 B가 2의 배수이거나 10으로 나눴을 때 나머지가 1이어야 한다.

따라서 이 연산을 반복해서 A가 될 수 있는가를 판단한다.
또한 중간 무한 루프로 돌 수도 있기 때문에 B가 A보다 작아지는 순간 루프를 빠져나오도록 한다.

import java.util.*;
import java.io.*;

public class Main{


    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw =new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine()," ");

         int A = Integer.parseInt(st.nextToken());
         int B = Integer.parseInt(st.nextToken());

         int cnt =0;

         while(A!=B){

             if(B%2!=0 && B%10 !=1){
                 cnt = -1;
                 break;
             }

             if(B<A){
                 cnt = -1;
                 break;
             }

             if(B%2==0){
                 B=B/2;
             }

             else if(B%10==1){
                 B=B/10;
             }
             cnt++;

         }

        if(cnt==-1) bw.write("-1");
        else {
            bw.write(Integer.toString(cnt+1));
        }

        bw.flush();
        bw.close();
        br.close();

    }


}