백준 No.16953 A->B (JAVA)

문제

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

- 2를 곱한다.

- 1을 수의 가장 오른쪽에 추가한다.

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

 

2 162

 

풀이

- A가 B로 가는 걸 구하는 건 정말 막막하다. 

- 거꾸로 생각해보면 쉬웠다. B-> A 가 되는 걸 구해보면 쉽게 구할 수 있다.
- 162가 2로 나눠질 경우

-  2로 나눠지지 않을 경우 -> (끝자리가 1로 끝나는지 안 끝나는지 안 끝날 경우 -1 출력)

162를 2로 나누면

81  -> 끝자리가 1로 끝남 1빼버림

8 -> 2로 나눠짐

4 -> 2로 나눠짐

2  끝 

 

카운트는 총 4번이고 여기서 1을 더해서 출력하면 됨 출력 조건에 그렇게 되어음

import javax.swing.plaf.synth.SynthOptionPaneUI;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
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 count = 0;

        while (true){
            if(B == A){
                count++;
                break;
            }
            if(B%2 == 0){
                B = B/2;
                count++;
            }else{
                String temp = Integer.toString(B);
                if(temp.charAt(temp.length() - 1) == '1'){
                    B= Integer.parseInt(temp.substring(0,temp.length()-1));
                    if(B < A){
                        count = -1;
                        break;
                    }
                    count++;

                }else{
                    count = -1;
                    break;
                }
            }
        }

        System.out.println(count);
    }
}