[백준] Greedy: A → B

문제

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

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

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

입력

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

출력

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

 

문제 접근

주어진 A에 2를 곱하거나 오른쪽에 1을 붙여서 B가될 때 까지의 연산 횟수+1을 반환해야 한다.

만들수 없는 경우 -1을 반환해야 한다.

동일한 로직이 특정 조건까지 반복되어야 하기 때문에 재귀함수 or while문으로 처리할 수 있다.

 

B를 A로 만들기 위해서는 다음과 같은 로직이 필요하다.

B가 짝수이면 2로 나눈다.

B가 홀수일 때 1의자리가 1인 경우 맨 오른쪽에 있는 1을 제거(B를 10으로 나눈 몫)

 

루프를 종료할 수 있는 조건은 다음과 같다.

B가 A와 같은 경우

B가 A*2보다 작은 경우(다음 연산을 위해 B를 2로 나누면 A보다 작아짐)

B가 홀수일 때 1의 자리가 1이 아닌 경우 A를 만들 수 없음.

 

재귀함수, while문 두 가지로 작성했다.

 

재귀함수

package baekjun;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class _16953 {

    static long count=0L;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        long A = Long.parseLong(s[0]);
        long B = Long.parseLong(s[1]);

        if (B < A*2L){
           count = -1L;
        }else{
            if (B%2L != 0L ){//홀수
               long end = B%10L;
                //1의 자리가 1인 경우
                if (end == 1){
                    findCount(A, B);
                }else{
                    //그렇지 않은 경우 : -1
                    count = -1L;
                }
            }else{//짝수
                findCount(A, B);
            }
        }
        System.out.println(count);
    }
    
    private static void findCount(long A, long number){
        //탈출 조건
        if (number == A){
            count++;
            return;
        }else if (number < 2L*A){
            count = -1L;
            return;
        }

        //짝수이거나
        if (number % 2 == 0){
            count++;
            findCount(A, number/2L);
        }else{ //홀수 인 경우
            if (number%10 == 1){
                count++;
                findCount(A, number/10L);
            }else {
                count = -1;
                return;
            }

        }

    }
}

 

while

package baekjun;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class _16953_v2 {

    static long count=0L;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        long A = Long.parseLong(s[0]);
        long B = Long.parseLong(s[1]);

        if (B < A*2L){
            count = -1L;
        }else{

            while(true){
                //판단
                if (B == A){
                    count++;
                    break;
                }else if (B < A*2L){
                    count = -1L;
                    break;
                }

                if (B%2L != 0L){

                    if (B%10L == 1L){
                        count++;
                        B /= 10L;
                    }else{
                        count = -1L;
                        break;
                    }

                }else{ //짝수
                    count++;
                    B /= 2L;
                }
            }

        }
        System.out.println(count);
    }


}