[알고리즘]백준16953 A → B -java

문제

생각

숫자 a에서

연산1. a=a*2

연산2. a= Integer.palseInt(String.valueof(a)+1)

연산1과 연산2중 선택해서 A가 B가 되도록하는 연산의 횟수를 구하는문제다.

만약 A가 4이고 B가 162일때
A가 연산1을 선택할지 연산2를 선택해야할지 알 수가없다.

이때 생각한 방법은 2가지다.

1. 이진트리를 사용해서 연산1,연산2를 둘다 계산해서 저장하는 방법
   모든경우의 수를 계산해서 트리방식으로 저장, a==b인경우가 나왓을때 그 노드의 깊이를 출력

2. B부터 역으로 계산하는 방법
   B가 2의 배수이면 나누기2, B의마지막자리가 1로끝나면 마지막자리제거
   B가 2의배수가 아니고, 1로끝나지않으면 -1출력

나는 2번방법을 선택했다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        
        String context = br.readLine();
        
        String[] contextList =context.split(" ");
        int A=Integer.parseInt(contextList[0]);
        int B=Integer.parseInt(contextList[1]);
        int count =0;
        
        while(A<B){
            if(B%2==0){
                B/=2;
                count++;
            }
            else{
                String stringB= String.valueOf(B);
                String rastStringB = stringB.substring(stringB.length()-1,stringB.length());
                if(rastStringB.equals("1")){
                    stringB=stringB.substring(0,stringB.length()-1);
                    count++;
                    B=Integer.parseInt(stringB);
                }
                else{
                    break;
                }

            }
        }
        
        if(A==B){
            System.out.println(count+1);
        }
        else{
            System.out.println(-1);
        }
    }
}