백준 16953번 A -> B(자바) - bfs

A → B 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

22531

9440

7561

40.492%

문제

정수 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

---

try {
    if (Integer.parseInt(tmp) <= b)
        que.offer(new Num(Integer.parseInt(tmp), now.cnt + 1));
}catch (NumberFormatException e) {
}catch (Exception e) {
    e.printStackTrace();
}

다음과 같이 try catch절을 만들어주지 않으면 numberFormatException이 발생한다

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

class Num {
    int num;
    int cnt;
    Num(int num, int cnt) {
        this.num = num;
        this.cnt = cnt;
    }
}
public class Main {
    static int b;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        b = sc.nextInt();
        bfs(a);
    }

    static void bfs(int start) {
        Queue<Num> que = new LinkedList<>();
        que.offer(new Num(start, 0));
        while (!que.isEmpty()) {
            Num now = que.poll();
            if (now.num == b) {
                System.out.println(now.cnt + 1);
                return;
            }
            if (now.num * 2 <= b)
                que.offer(new Num(now.num * 2, now.cnt + 1));
            String tmp = Integer.toString(now.num) + '1';
            try {
                if (Integer.parseInt(tmp) <= b)
                    que.offer(new Num(Integer.parseInt(tmp), now.cnt + 1));
            }catch (NumberFormatException e) {
            }catch (Exception e) {
                e.printStackTrace();
            }

        }
        System.out.println(-1);
    }
}