[백준] [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 boolean [] visited;
	static HashMap<Long, Integer> dap;
	static long A, B;
	
	static void BFS(long s) {
		Queue<Long> q = new LinkedList<>();
		q.offer(s);
		dap.put(s, 1);
		while(!q.isEmpty()) {
			long now = q.poll();
			
			long nextP1 = now * 2;
			long nextP2 = Long.parseLong(String.valueOf(now) + String.valueOf(1));
			
			if(nextP1 <= B && !dap.containsKey(nextP1)){
				q.offer(nextP1);
				dap.put(nextP1, dap.get(now)+1);
			}
			if(nextP2 <= B && !dap.containsKey(nextP2)) {
				q.offer(nextP2);
				dap.put(nextP2, dap.get(now)+1);
			}
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		dap = new HashMap<>();
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		
		BFS(A);
		int result = -1;
		
		if(dap.containsKey(B)) result = dap.get(B);
		
		System.out.println(result);
	}

}

 

※생각정리

 

입력된 A값에 곱하기 2 또는 뒤에 1을 붙인수로 계속해서 값을 이어 붙여 큐에 담았다. 연산한 값이 B값을 넘으면 더이상 큐에 담지 않으면서 같은 방법을 반복했다.

 

배열에 담으면 메모리초과를 피할 수 없기 때문에 필요한 값만 담기위해 HashMap을 이용해 해당 숫자까지 오는데 걸린 가중치를 담았다.

 

 

 

 

-새벽코딩-