[백준/Silver II] A → B - 16953

[Silver II] A → B - 16953

문제 링크

성능 요약

메모리: 22564 KB, 시간: 204 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 그리디 알고리즘

제출 일자

2024년 12월 9일 17:18:21

문제 설명

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

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

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

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

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

 

 

 

 

 

---

풀이 및 코드

연산은 2를 곱하거나 1을 더하거나 원래의 값이 더 커질 수 밖에 없다.

즉, 원래의 값이 B보다 크면 탐색을 이어갈 필요가 없다.

 

이 문제에서 주의해야 할 것은, A와 B의 범위가 10^9라는 것.

때문에 long 타입으로 계산해야한다.

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

public class Main {
    private static long bfs(int n, int target){
        if(n == target) return 1;
        Queue<long[]> queue = new LinkedList<>();
        queue.add(new long[]{n, 1L});
        long result = -1;
        long[] info;
        while(!queue.isEmpty()){
            info = queue.poll();
            // 다음 연산 결과가 target과 같으면 연산 값 return
            if(info[0] * 2 == target || info[0]*10+1 == target) return info[1]+1;
            // 연산 결과가 target보다 작을 때만 다음 연산 추가
            if(info[0] * 2 < target) queue.add(new long[]{info[0]*2, info[1]+1});
            if(info[0] * 10 + 1 < target) queue.add(new long[]{info[0]*10+1, info[1]+1});

        }
        return result;

    }


    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        br.close();
        System.out.print(bfs(input[0], input[1]));
    }
}