[백준] A → B

문제 주소

https://www.acmicpc.net/problem/16953

16953번: A → B

문제 설명

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

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

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

입력

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

출력

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

예제 입력 1

2 162

예제 출력 1

5

2 → 4 → 8 → 81 → 162

예제 입력 2

4 42

예제 출력 2

-1

예제 입력 3

100 40021

예제 출력 3

5

100 → 200 → 2001 → 4002 → 40021

 

제출 코드

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

public class Main {

    static long min = Long.MAX_VALUE;
    static long target;

    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Integer.parseInt(st.nextToken());
        target = Integer.parseInt(st.nextToken());

        search(n);

        if(min==Long.MAX_VALUE){
            min = -1;
        }

        System.out.println(min);

    }

    public static void search(long n){
        int count = 0;

        ArrayList<Long> list = new ArrayList<>();
        ArrayList<Long> next;

        list.add(n);

        while(!list.isEmpty()){

            count++;
            next = new ArrayList<>();

            for(long i : list){
                if(i>target){
                    continue;
                }else if(i==target){
                    min = count;
                    return;
                }
                next.add(i*10+1);
                next.add(i*2);
            }

            list = next;
        }
    }
}

코드 설명

search 함수에서 BFS를 돌린다

i가 target보다 크면 더 할 필요가 없으므로 continue로 넘기고

i가 target과 같으면 전역변수에 넣어주고 리턴한다

그 외의 경우에는 1을 붙인 값과 2를 곱한 값을 next에 넣어준다

q의 모든 자식노드가 next에 들어있는데

next를 q에 넣어서 다음 level을 search하게 한다

 

풀이과정

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

public class Main {

    static int min = Integer.MAX_VALUE;
    static int target;

    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        target = Integer.parseInt(st.nextToken());

        search(n);

        if(min==Integer.MAX_VALUE){
            min = -1;
        }

        System.out.println(min);

    }

    public static void search(int n){
        int count = 0;

        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> next;

        list.add(n);

        while(!list.isEmpty()){

            count++;
            next = new ArrayList<>();

            for(int i : list){
                if(i>target){
                    continue;
                }else if(i==target){
                     min = count;
                    return;
                }
                next.add(i*10+1);
                next.add(i*2);
            }

            list = next;
        }
    }

}

처음에는 이렇게 풀었는데 제출하니까 틀렸다

overflow가 일어났나..?

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

그런듯함 10의 9승이면 Integer의 끝인데

거기다가 10을 곱했다고 생각하면 범위 초과임

 

✨Long으로 바꿔주고 맞았다