[백준] 16953번 : A -> B

 

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

16953번: A → B

 

문제

 

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

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

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

 

입력

 

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

 

출력

 

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

 

 

풀이 방법

 

문제의 해결을 위해 A->B로 바꾸기 위해 많은 경우의 수를 고려해봤는데 답이 떠오르지 않았다.

다른 풀이를 약간 참고해보니 B로부터 A를 도출하는 아이디어를 사용하였다.

경우의 수로는 B%2==0, B%10==1, 그 외의 경우로 총 3가지를 들 수 있었다.

규칙성을 발견하기 어려울때는 역발상의 아이디어를 참고해야겠다.

 

작성 코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

package baekjoon.greedy;   import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BJ_16953 {       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 count=1;           while (true){             if(A==B){                 System.out.println(count);                 return;             }             if(A>B){                 System.out.println(-1);                 return;             }               if(B%2==0){                 B=B/2;             } else if (B%10==1){                 B=B/10;             }  else {                 System.out.println(-1);                 return;             }             count++;         }       } }