[Java] 백준 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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static int A, B, result;
	
	public static void main(String[] args) throws IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(br.readLine());
		
		A=Integer.parseInt(st.nextToken());
		B=Integer.parseInt(st.nextToken());
		result=Integer.MAX_VALUE;
		
		dfs(0, A);
		if(result==Integer.MAX_VALUE) System.out.println(-1);	// 결과가 int의 MAX 값이면 만들 수 없는 경우이므로 -1을 출력
		else System.out.println(result+1);	// 만들 수 있는 경우 결과값을 출력
	}

	private static void dfs(int cnt, long val) {	// cnt : 현재까지 연산 횟수, val : 현재 수
		if(cnt>=result) return;	// 연산 횟수가 현재 result값보다 크거나 같으면 최솟값이 될 수 없으므로 리턴
		if(val>B) return;	// 현재 수가 B보다 크면 만들 수 없는 경우이므로 리턴
		if(val==B) {	// B를 만든 경우
			result=Math.min(result, cnt);	// 연산의 최솟값을 구함
			return;
		}
		
		dfs(cnt+1, val*2);	// 2를 곱하는 연산
		dfs(cnt+1, val*10+1);	// 1을 수의 가장 오른쪽에 추가하는 연산
	}
}

dfs를 통해 2를 곱하는 연산과 1을 수의 가장 오른쪽에 추가하는 연산을 수행합니다. 연산 수행시에 조건을 벗어나는 경우가 발생하면 리턴합니다.

 

<조건을 벗어나는 경우>

1. 최솟값이 될 수 없는 경우

2. B보다 값이 커진 경우