[백준/자바] 16953번 A → B

 

 

 

설명

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

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

 

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

 

 

 

입력

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

 

 

 

출력

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

 

 

 

예시 입력1

2 162

 

 

 

예시 출력1

5

 

 

 

 

예시 입력2

4 42

 

 

 

 

예시 출력2

-1

 

 

 

 

예시 입력3

100 40021

 

 

 

예시 출력3

5

 

 

 

 

풀이

핵심은 B에서 A를 만들어 낸다는 것이다.

B가 A보다 클 때 까지만 반복한다. B의 일의 자리(마지막 숫자)가 1일 때는 10으로 나누고, B의 일의 자리(마지막 숫자)가 짝수일 때는 2로 나눈다. 즉, A에서 B를 만들 때 했던 행위의 반대의 행위를 하면 된다.

 

A와 B가 같다면 현재 count에서 +1을 한 값을 리턴하고 그렇지 않다면 -1을 리턴한다.

 

 

코드

package baekjoon._16953;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    public static int solution(long A, long B) {
        int count = 0;

        while (B > A) {
            if (B % 10 == 1) {
                B /= 10; // 마지막 숫자가 1일 때, 10으로 나눔
            } else if (B % 2 == 0) {
                B /= 2; // B가 짝수일 때, 2로 나눔
            } else {
                return -1; // 위의 두 경우에 해당하지 않으면 A에서 B를 만들 수 없음
            }
            count++;
        }

        if (A == B) {
            return count + 1; // A와 B가 같으면 연산 횟수 + 1 반환
        } else {
            return -1; // 같지 않으면 -1 반환
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());

        sb.append(solution(A, B));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}