[BOJ] 16953 A->B (Java)

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

 

A에서 B를 만드는 방법은 여러개이고, 현재 값에서 다음 값으로 갈때 어떤 연산을 해야 더 빠른지 알 수 없다.

하지만 역순으로 생각하면 다르다! B에서 1이 있으면 무조건 1을 더하는 연산을 쓸 수 밖에 없으니 이 연산을 우선순위로 두고 나아가면 된다.

즉, B -> A로 가면서 1이 있으면 1을 제외하고, 1이 없으면 2를 나누고, 두 연산 다 되지 않거나 B의 연산값이 A보다 작아지면 -1을 출력한다.

 

<제출 코드>

package BOJ.Greedy;

import java.util.Scanner;

public class BOJ_16953_AtoB {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        int cnt = 0;
        // 1이 있으면 1을 빼주고, 없으면 2로 나눠줌
        while(true){
            // a가 만들어진 경우
            if(b == a) break;
            // a로 만들 수 없는 경우
            if(b < a) {
                cnt = -2;
                break;
            }
            // 1이 있는 경우
            String strB = Integer.toString(b);
            int len = strB.length();
            if(strB.charAt(len-1) == '1') {
                cnt++;
                strB = strB.substring(0, len-1);
                b = Integer.parseInt(strB);
            }
            // 2로 나누어지는 경우
            else if(b % 2 == 0){
                cnt++;
                b = b / 2;
            }
            // 두 연산 다 안되는 경우
            else {
                cnt = -2;
                break;
            }
        }
        System.out.println(cnt+1);
    }
}