[Baekjoon] 16953번: A -> B - Java

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

16953번: A → B

문제 설명

정수 A와 B가 주어진다. 그리고 A를 B로 만들려고 하는데 가능한 연산 규칙은 다음 두 가지다.

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

A를 B로 바꾸는데 필요한 연산의 최솟값을 구하면 된다.

풀이 방법

A를 B로 만드는 것보다 B를 A로 만드는 게 더 편할 것 같다는 생각으로 반복문을 통해 해결했다. 예전이 이와 비슷한 방법으로 해결했던 문제가 있었다. https://somuchthings.tistory.com/181 (지금보니 이 문제 이름도 'A와 B' 였다 ㅎㅎ)

위 규칙에 따르면 1의 자리 숫자가 1이 아닌 홀수는 나올 수 없으므로 이 경우 -1을 출력하도록 했다. 그다음에는 B가 짝수이면 2로 나누고 1로 끝난다면 1을 빼고 10으로 나누는 방법으로 1을 제거했다.

package baekjoon.greedy;

import java.io.*;

public class BOJ16953 {

    static long A, B;

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String[] split = br.readLine().split(" ");
            A = Long.parseLong(split[0]);
            B = Long.parseLong(split[1]);

            int cnt = 1;
            while (A < B) {
                // 1이 아니면서 홀수인 수는 만들어질 수 없다
                if (B % 10 != 1 && B % 2 == 1) {
                    System.out.println(-1);
                    return;
                }
                if (B % 2 == 0) {
                    B = B / 2;
                } else {
                    B = B - 1;
                    B = B / 10;
                }

                cnt++;
            }
            System.out.println(A == B ? cnt : -1);
        }
    }
}