[JAVA] 백준 q16953 - A → B

16953번: A → B

---

의식의 흐름

A에서 B로 가면 경우의 수가 너무 많을 것 같으니까 B에서 A로 가볼까..?

일의 자리가 1이거나 짝수일 때만 연산 가능하니까 그 경우만 처리해주고 나머지는 -1이겠지!

 

풀이

B를 A로 만들기 도전

1. B의 일의 자리가 1인 경우 1을 없애주고, B가 짝수인 경우 2로 나누어준다.

   만약, 2가지 경우 중 하나에 포함되지 않는 경우(ex. 일의 자리가 3인 경우)는 A로 만들지 못하는 경우이므로 -1 출력

2. 1번 연산을 B<A 또는 B==A일 때까지 반복한다.

 

코드

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

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());
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        int cnt = 1;
        while(true){
            if(B%10==1) // 일의 자리가 1인 경우
                B = (B-1)/10;
            else if(B%2==0) // 짝수인 경우
                B /= 2;
            else {
                bw.write("-1");
                break;
            }
            cnt++;

            if(B<A){ // 만들 수 없는 경우
                bw.write("-1");
                break;
            }
            else if(B==A){ // 만든 경우
                bw.write(Integer.toString(cnt));
                break;
            }
        }

        bw.flush();
    }
}