[백준] no16953: A -> B

문제

시작 숫자 A와 목표 숫자 B가 주어진다.
A가 B로 될 때까지 발생하는 연산의 최소값을 구하시오

연산 방법은 다음 두가지 뿐이다.
1. A * 2
2. A의 뒤에 1을 추가  (즉, A가 2일 경우, 21이 되는 연산)

단, 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

---

원리

필자 : BFS를 이용해 풀이했다.

Chat CPT : 조건문으로 해결했다.

---

풀이방법

1. 바뀐 숫자를 넣을 Num, 몇번째 연산인지 Count할 Cnt변수를 가진 Node클래스를 만든다.
2. BFS를 이용해 순차적으로 연산해준다.
3. 이때, BFS는 Deque라는 대기열을 사용해 연산해주며,
   가장 먼저 목표 숫자인 B에 도달한 숫자는 가장 적게 Count된 객체가 될 것이다.

* 단, 연산의 범위 문제상 BigInteger를 사용했다.
  이에 따라 방문체크로 중복을 방지할 boolean형 배열을 사용하지 못했다.

* 개선점으로는 int형을 사용하되, 2번째 방법의 연산에서 만약 String 타입으로 된 숫자가 int범위를 넘는다면,
  Deque에 넣지 않는 방식을 사용하는 방법이 있다.

---

나의 코드

private static BigInteger A;
private static BigInteger B;
private static BigInteger min = BigInteger.valueOf(-1);

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    A=new BigInteger(st.nextToken());
    B=new BigInteger(st.nextToken());
    BFS();

    System.out.println(min);
}

/**
 * Deque 대기열을 이용
 * Node 객체에 변형된 숫자와 연산 수를 담아 순차적으로 처리한다.
 * 이때, Deque에 두 가지 방식의 연산으로 각각 넣어주고 계산 시키는 방식이다.
 * 만약 제일 먼저 목표 숫자에 도달한다면, 연산 횟수 Cnt는 순차적으로 증가해서 들어가는 대기열이므로, 최소값이 되는 원리이다.
 * 
 * 단, BigInteger를 사용할 경우, 연산에 사용될 숫자 범위가 제한되지 않으나,
 * 방문체크를 활용한 중복 연산을 방지하는 코드가 들어가질 못하고,
 * BigInteger는 하나의 객체이므로. 타입 변환 과정에 필요한 메모리가 추가되어 메모리 소모가 있다.
 */
private static void BFS() {
    Deque<Node> dq = new ArrayDeque<>();
    dq.add(new Node(A, BigInteger.valueOf(1)));

    while(!dq.isEmpty()) {
        Node now = dq.poll();
        if(now.Num.compareTo(B)==0) {
            min = now.Cnt;
            break;
        }

        if(now.Num.compareTo(B) == -1) {
            dq.add(new Node(now.Num.multiply(BigInteger.valueOf(2)), now.Cnt.add(BigInteger.valueOf(1))));

            String nowStr = now.Num + "1";
            BigInteger now1 = new BigInteger(nowStr);
            dq.add(new Node(now1, now.Cnt.add(BigInteger.valueOf(1))));
        }
    }
}

/**
 * BFS 대기열에 넣을 객체를 생성해주기 위한 이너클래스
 */
private static class Node {
    private BigInteger Num;
    private BigInteger Cnt;

    public Node(BigInteger num, BigInteger cnt) {
        this.Num = num;
        this.Cnt = cnt;
    }
}

---

Chat GPT 코드

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] input = br.readLine().split(" ");
    int A = Integer.parseInt(input[0]);
    int B = Integer.parseInt(input[1]);

    int cnt = 0;

    while (true) {
        if (A == B) { // A와 B가 같은 경우
            System.out.println(cnt+1); // cnt에 1을 더한 값을 출력
            break;
        } else if (B < A) { // B가 A보다 작은 경우, 더 이상 계산이 불가능함
            System.out.println(-1); // -1 출력
            break;
        } else if (B % 2 == 0) { // B가 짝수인 경우, 2로 나눔
            B /= 2;
            cnt++;
        } else if (B % 10 == 1) { // B의 일의 자리가 1인 경우, 1을 제거함
            B /= 10;
            cnt++;
        } else { // B가 2로 나누어지지 않고 일의 자리가 1이 아닌 경우, 더 이상 계산이 불가능함
            System.out.println(-1); // -1 출력
            break;
        }
    }

    br.close();
}