[백준 16953] A → B with JAVA

www.acmicpc.net/problem/16953

16953번: A → B

문제

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

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

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

입력

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

출력

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

 

import java.io.*;
import java.util.*;

public class P16953_A_to_B {
    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 cnt = 1;
        while (A != B){
            if (B < A) {
                System.out.println(-1);
                System.exit(0);
            }
            if (B % 10 == 1) B /= 10;
            else if (B % 2 == 0) B /= 2;
            else {
                System.out.println(-1);
                System.exit(0);
            }
            cnt++;
        }
        System.out.println(cnt);
    }
}

1. 어려웠던 점:

- 그리디 식 접근

 

2. 알게된 점:

- 그리디 복습

 

3. 알고리즘 풀이:

- 뒤에서부터 거꾸로 접근한다.

B의 일의 자리가 1이면 (B % 10 = 1) 일의 자리를 없앤다. (B /= 10)

그렇지 않고, B가 2로 나뉜다면 (B % 2 = 0) 2로 나누어준다. (B /= 2)

둘 다 못한다면, B는 절대로 A가 될 수 없다.

A가 B로 나아가는 수단은 위 두 가지 밖에 없기 때문이다.

 

혹은, 위 과정을 거쳤지만 B가 A보다 작아진다면, 이 또한 B는 절대로 A가 될 수 없다.