P.16953 A -> B

코드

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;

public class P_16953 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        long a = arr[0], b = arr[1];

        bw.write(Long.toString(bfs(a, b)));
        bw.flush();
    }

    private static long bfs(long a, long b) {
        LinkedList<long[]> queue = new LinkedList<>();
        queue.add(new long[]{a, 0});

        while (!queue.isEmpty()) {
            long[] poll = queue.poll();

            if (poll[0] == b) return poll[1] + 1;

            if (poll[0] * 2 <= b) queue.add(new long[]{poll[0] * 2, poll[1] + 1});
            if (poll[0] * 10 + 1 <= b) queue.add(new long[]{poll[0] * 10 + 1, poll[1] + 1});
        }

        return -1;
    }
}

코드 설명

연산의 최솟값을 구하라고 했으니 bfs를 이용했다.

 

문제 구현 자체에서 특별한 건 딱히 없고, 하나 신경써야 할 것은 long으로 계산을 해야한다는 것이다.

int로 할 시 10^9 - 1로 문제에 제시된 연산을 할 경우 범위를 넘게 되어 에러가 발생한다.