[BOJ 16953] A -> B (Java)

---

문제 링크

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

16953번: A → B

---

풀이

- A, B (1 ≤ A < B ≤ 10^9)의 경우 Integer로 처리 가능

- BFS로 카운팅 배열 처리하는 문제인 줄 알았으나 '메모리 초과' 발생 

- 배열 대신 B -> A 로 감소 시키면서 카운팅 처리하도록 풀이 

1) 2 를 곱하는 경우는 => 2로 나누어지는 경우 2로 나누기 

2) 끝자리에 1을 붙이는 경우는 => 끝자리가 1인 경우 10 으로 나누기 (*Java 에서는 실수값 나누기할 경우 실수만 취급)

 

 

*실수

B 값이 2로 나누어지지 않거나, 끝자리가 1이 아닌 경우는 답을 구할 수 없으므로 while 반복문 종료 후 -1 출력해야 함

 

이걸 판단 못해서 삽질 :(

 

참고

https://steady-coding.tistory.com/11

[BOJ] 백준 16953번 : A -> B (JAVA)

---

제출 코드

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

public class Main {
    
    static int A, B;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        
        br.close();
    }

    static void func() {
        boolean find = true;
        int cnt = 1;
        while(A != B) {
            if(B < A) {
                find = false;
                break;
            }

           String str = String.valueOf(B);
           if(str.charAt(str.length() - 1) != '1' && B % 2 != 0) {
                find = false;
                break;
           }

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

        System.out.println(!find ? -1 : cnt);
    }

    static void pro() {
        func();
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}