[Algorithm] 백준 16953번_A->B(Java)

1. 🔗 16953번 A -> B

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

16953번: A → B

 

2. 문제

---

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

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

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

 

3. 입력

---

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

 

4. 출력

---

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

 

5. 📝 접근 방법 및 풀이

---

처음에는 A를 B로 바꾸는 방식으로 하려 했지만, 거꾸로 B를 A로 바꾸는 로직이 더 빠를 것 같아서 그렇게 해보았습니다.

1. B가 2로 나누어 떨어지면,
   1. B를 2로 나눈다.
   2. 횟수 += 1
2. B의 끝자리가 1이면,
   1. 1을 제거한다.
   2. 횟수 += 1
3. 나머지 경우는 -1 출력 후 종료

 

6. 💻 코드

---

      

      

      

    
    

      <java />
    
 import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.util.StringTokenizer;
 
 public class Main {
     public static void main(String[] args) throws IOException {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(br.readLine());
 
         int A = Integer.parseInt(st.nextToken());
         int B = Integer.parseInt(st.nextToken());
 
         int answer = 1;
         while (B != A) {
             if( B < A ) {
                 System.out.println(-1);
                 return;
             }
             String str = String.valueOf(B);
             if(B % 2 == 0) {
                 B /= 2;
             } else if(str.charAt(str.length() - 1) == '1') {
                 str = str.substring(0, str.length() - 1);
                 B = Integer.parseInt(str);
             } else {
                 System.out.println(-1);
                 return;
             }
             answer++;
         }
 
         System.out.println(answer);
     }
 }