BOJ_S2_16953

📁 [S2_16953] A -> B

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

public class Main {
    static int A,B;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        // **** input start ****

        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        // **** input end ****

        dp(A,1);

        // 만약 값이 없으면 -1 출력
        if(min == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(min);
    }

    // dp
    static void dp(long num, int cnt){
        // B보다 크면 통과
        if(num > B){
            return;
        }

        // B이면 최소값 입력
        if(num == B){
            min = Math.min(min, cnt);
            return;
        }


        // 2 곱하기
        dp(num*2,++cnt);
        // 백트래킹
        cnt--;

        // 1을 수 가장 오른쪽에 추가
        dp(num*10+1, ++cnt);
        // 백트래킹
        cnt--;
    }
}

🤔 나의 생각

보자마자 A,B의 범위가 10의 9승인 것을 보고 재귀로 풀었다.
확실히 문제를 많이 풀다 보니 감이 잡히는 것 같다 ㅎㅎ
풀이 과정이다.

• A부터 카운팅을 해준다.
• 곱하기 2로 하나 , 1을 가장 오른쪽에 추가하는 거 하나 로 계속해서 펼쳐 나간다.
• 만약 B보다 큰 값이 다시 호출된다면 return 해준다.
• 만약 B값에 도달하면 기존 값과 비교해서 min 값을 구해준다.
• 마지막에 min 출력하면 끝

처음에 dp[] 배열을 이용해 풀었는데 메모리 초과가 떴다.. 그래서 생각해보니 굳이 배열을 구할 필요가 있을까 라는 생각과 함께 그냥 B에 도달해주면 최솟값을 비교해주는 식으로 했다.
그리고 A,B의 범위가 int 범위를 넘어서기 때문에 long을 사용해서 num을 구해줘야 하는 것이 포인트다.