hongjunland

Welcome

1 분 소요

백준 16953

제한

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 12707 5379 4277 40.629%

문제

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

2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

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

출력

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

예제 입력1

2 162

예제 출력1

5

예제 입력2

4 42

예제 출력2

-1

예제 입력3

100 40021

예제 출력3

5

풀이

A에서 B로 가는데, 2를 곱했을 경우와 1을 붙였을 경우 가지치기 방식으로 풀이를 해보려 한다.

B 까지 가는 데에 최소경로를 구하기 때문에, DFS방식보단 BFS방식으로 했다.

왜냐하면, DFS방식으로 모든 경우의 수를 왔다갔다하면서 최솟값을 구하는것 보단, BFS방식으로 Depth 마다 발견되는 순간 종료조건이 되는 것이 좀 더 효율적이라 판단해서 BFS를 택했다.

소스코드


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 BJ_16953_Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long A = Integer.parseInt(st.nextToken());
        long B = Integer.parseInt(st.nextToken());
        int result = -1;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(A,0));

        while (!queue.isEmpty()){

            Node node = queue.poll();
            long num = node.num;
            int d = node.depth;

            if(num==B){
                result = d+1;
                break;
            }
            if(num*2<=B){
                queue.offer(new Node(num*2,d+1));
            }
            if(num*10+1<=B){
                queue.offer(new Node(num*10+1,d+1));
            }
        }
        System.out.println(result);

    }
    static class Node{
        long num;
        int depth;
        public Node(long num, int depth) {
            this.num = num;
            this.depth = depth;
        }
    }
}

참고