[백준] 16953번 : A -> B - 자바(JAVA)

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

16953번: A → B

 

문제 해석

정수 A와 B가 주어집니다.

 

A로 B를 만드려고 하는데 두가지 연산을 수행할 수 있습니다.

A * 2

A * 10 + 1

 

이때 필요한 연산의 최솟값을 구해보려고 합니다.

 

문제 풀이 전 설계

Queue를 사용하고 Number 객체를 만들어 (현재 수, 연산의 step)을 관리합니다.

 

이때 수는 항상 커집니다.

따라서 Queue에 add하기 전에 현재 수가 B보다 큰 경우에는 add하지 않습니다.

 

그리고 B가 10억까지 주어질 수 있습니다.

A를 연산하는 과정에 overflow가 발생할 수 있어서 long 타입을 고려해야 합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static class Number {
        long num;
        int step;

        public Number(long num, int step) {
            this.num = num;
            this.step = step;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        Queue<Number> bfsQ = new LinkedList<>();

        bfsQ.add(new Number(A,1));
        int result = -1;

        while(!bfsQ.isEmpty()){
            Number cur = bfsQ.poll();
            if(cur.num == B){
                result = cur.step;
                break;
            }
            if(cur.num * 10 + 1 <= B) {
                bfsQ.add(new Number(cur.num * 10 + 1, cur.step + 1));
            }
            if(cur.num * 2 <= B) {
                bfsQ.add(new Number(cur.num * 2, cur.step + 1));
            }
        }

        System.out.println(result);

    }


}