[백준 16953] A → B (Java)

---

풀이

이 문제는 정수 A를 B로 바꾸는데 필요한 연산의 최소값을 구하는 문제이다. 얼핏보면, DP를 활용하여 문제를 해결할 수 있을 것 같지만, 이는 잘못된 생각이다.

왜냐하면 A와 B의 범위가 $10^9$이하이기 때문에, 시간복잡도가 $O(N)$의 형태인 DP에서는 시간초과가 발생할 수 밖에 없기 때문이다.

따라서, 이 문제는 BFS로 접근해야 해결할 수 있다.

또한 A와 B의 범위가 $10^9$이하이기 때문에, $1 \sim 10^9$의 숫자에 대해 최소 연산 횟수를 기록한다면 메모리가 1GB가 필요하기 때문에, 메모리 초과가 발생할 수 있다.

따라서, 최소한의 숫자만 연산 횟수를 기록해야하므로 Map을 이용해야한다.

그리고 추가로 주의해야할 점은 이 문제에서는 A가 대단히 크기 때문에 다음 위치의 값을 계산하다가 오버플로우가 발생할 수 있다.

따라서 다음 값은 long타입으로 변환하여 계산하는 것이 옳다.

이제 문제에서 요구한대로 $A \times 2$와 $A \times 10 + 1$을 다음 값으로하여, 이 두 값들이 $B$보다 작거나 같은지와 이미 최소 연산 횟수가 구해져 있는지 여부를 판단하여, 큐에 삽입 여부를 결정한다.

BFS로 문제를 해결하고 있으므로 현재 값인 current를 이용해 다음 값인 next를 구했다면, 연산 횟수는 1증가할 수 밖에 없다. 즉, 이미 방문한 수들의 최소 연산 횟수는 다음에 방문할 수들의 최소 연산 횟수보다 작을 수 밖에 없다는 것이다.

따라서, $A \times 2, A \times 10 + 1 \le B$를 만족하면서, Map에 next가 키로 존재하지 않아야 큐에 삽입할 수 있다는 의미이다.

이를 코드로 옮겨보면 다음과 같다.

import java.util.*;
import java.io.*;

class InputHandler {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer st;
    
    public static int nextInt() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return Integer.parseInt(st.nextToken());
    }
}

class Solution {
    private static final Queue<Integer> q = new ArrayDeque<>();
    private static final Map<Integer, Integer> count = new HashMap<>();
    
    public static void bfs(int A, int B) {
        q.add(A);
        count.put(A, 0);
        while (!q.isEmpty()) {
            int val = q.poll();
            int cnt = count.get(val);
            if (val == B) {
                System.out.println(cnt + 1);
                return;
            }
            // 두배
            long next = 2l * val;
            if (next <= B && !count.containsKey(next)) {
                q.add((int)next);
                count.put((int)next, cnt + 1);
            }
            // 1을 오른쪽에 추가
            next = val * 10l + 1;
            if (next <= B && !count.containsKey(next)) {
                q.add((int)next);
                count.put((int)next, cnt + 1);
            }
        }
        System.out.println(-1);
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        int A = InputHandler.nextInt(), B = InputHandler.nextInt();
        Solution.bfs(A, B);
    }
}