[백준 Java] 16953 A → B

문제 링크

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

접근 방법

dfs를 사용한다.
종료 조건은 A,B가 같은 경우 최소 횟수를 갱신하고 리턴
dfs를 타는 부분은 2를 곱할때, 1을 뒤에 붙일때.

input이 10^9까지 들어오기 때문에 long으로 처리했다.
백트래킹은 횟수와 A의 크기를 비교해서 처리했다.

코드

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

public class Main {

    static int res;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(br.readLine());

        Long A = Long.parseLong(tokens.nextToken());
        Long B = Long.parseLong(tokens.nextToken());

        res = Integer.MAX_VALUE;

        dfs(A, B, 1);

        System.out.println(res == Integer.MAX_VALUE ? -1 : res);
    }
    private static void dfs(long A, long B, int cnt) {
        if (res < cnt || A > B) { //백트래킹
            return;
        }

        if (B == A) {
            res = Math.min(res, cnt);
            return;
        }
        //2를 곱함
        dfs(A * 2, B, cnt + 1);
        //끝에 1을 붙임
        dfs(Long.parseLong(Long.toString(A) + "1"), B, cnt + 1);
    }
}