16953 - A -> B[S2]

문제

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

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

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

풀이

 

BFS의 기본 변형 같은 문제.

두 가지의 경우의 수를 반복해서 탐색하면 된다. 이를 위해 PriorityQueue를 선언 후, Comparator로 최대값을 먼저 순회하도록 설정하였다.

 

그 외에 Long 타입 int 캐스팅 시 long 원시형으로 변형 후 두 번 변형해야 한다는 점 유의할 것.

코드

 

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

public class Main {
    static long N, M;
    static int result = -1;
    public static void main(String[] args) throws Exception {
        input();
        if(N == M) {
            System.out.println(1);
            return;
        }

        PriorityQueue<Long[]> pq = new PriorityQueue<>((l1, l2) -> -l1[0].compareTo(l2[0]));
        pq.add(new Long[] {(N * 2), 2L});
        pq.add(new Long[] {(N * 10 + 1), 2L});
        while(!pq.isEmpty()) {
            Long[] now = pq.poll();
            long value = now[0];
            int count = (int) (long) now[1];
            if(value == M) {
                result = count;
                break;
            }
            if(value < M) {
                pq.add(new Long[] {(value * 2), (long)(count + 1)});
                pq.add(new Long[] {(value * 10 + 1), (long)(count + 1)});
            }
        }

        if(result != -1) System.out.println(result);
        else System.out.println(-1);
}

static void input() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Long.parseLong(st.nextToken());
    M = Long.parseLong(st.nextToken());
}
}