[BOJ] 16953 - A → B

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/16953

16953번: A → B

난이도: 실버 1

사용언어: JAVA

 

풀이

굉장히 전형적인 다이나믹 프로그래밍 문제처럼 보이지만, 다이나믹 프로그래밍으로 해당 문제를 구현 시 메모리 초과가 나는 것을 확인할 수 있었습니다. 

 

이 문제는 다이나믹 프로그래밍이 아닌 그리디 알고리즘으로 접근을 해야 합니다. B에서부터 뒤에 1을 뗄 수 있으면 떼주고, 2로 나눌 수 있으면, 2로 나누어주면서 A까지 이동하는 것입니다. 물론 1을 떼는 것에 우선순위를 둡니다. 그리고 중간에 1을 뗄 수도, 2로 나눌 수도 없는 수가 나오면, -1을 출력해주면 됩니다.

 

import java.io.*;
import java.util.StringTokenizer;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int cnt = 1; // 문제에서 필요한 연산의 최솟값에 1을 더한 값을 출력하라고 했기 때문에 0이 아닌 1에서 부터 시작했습니다.
 
        while(B > A){
            if(B % 10 == 1 && B / 10 >= A){ // B에서 뒤에 1을 뗄 수 있으면
                B = B/10; // 떼준다
            }
            else if(B%2 == 0 && B / 2 >= A){ // B를 2로 나눌 수 있으면
                B = B/2; // 나눠준다
            }
            else{ // 둘 다 불가능하면
                bw.write("-1\n"); // B는 A가 될 수 없다.
                bw.flush();
                System.exit(0);
            }
 
            if(A == B){
                bw.write(String.valueOf(cnt+1)+"\n"); // 연산의 횟수 출력
                bw.flush();
                System.exit(0);
            }
            cnt++;
        }
    }
}