[백준 / JAVA] 16953번 A→B

이 글에는 백준 16953번 A→B문제에 대한 풀이와 정답 코드(JAVA)가 있습니다.

 

문제

정수 A를 B로 만들기

• 2를 곱한다
• 1을 수의 가장 오른쪽에 추가한다

A에서 B가 될때까지의 연산의 최솟값

A, B (1≤ A < B ≤ 10^9)

 

풀이

• 연산의 최솟값이라는 키워드가 주어졌기 때문에 BFS(너비 우선 탐색)으로 접근했습니다.
• A, B의 범위가 10^9 까지이기 때문에 자료형을 Long으로 해야 합니다.
• 1을 가장 오른쪽에 추가할 때는 (현재값*10) + 1을 사용하면 됩니다

 

전체 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_16953_AB_BFS {

    public static void main(String[] args) {
        Scanner scann = new Scanner(System.in);
        long A = scann.nextLong();
        long B = scann.nextLong();

        Queue<Long> que = new LinkedList<>();
        que.add(A*2);
        que.add(A*10+1);

        int answer = 0;
        while(!que.isEmpty()) {
            answer++;
            int size = que.size();

            for (int i = 0; i < size; i++) {
                long now = que.poll();
                if(now>B) continue;
                if(now==B) {
                    System.out.println(answer+1);
                    return;
                }
                que.add(now*2);
                que.add(now*10+1);
            }
        }
        System.out.println(-1);
    }
}

16953번: A → B

16953번: A → B