백준 16953번 : A -> B

 문제

www.acmicpc.net/problem/16953

16953번: A → B

16935 A->B

 

 구현 방법

 dfs로 구현하였습니다. 2가지의 연산을 할 수 있기 때문에 2가지 경우를 다 구해주었습니다. 2는 그냥 단순히 곱하면 되고 1을 수의 가장 오른쪽에 추가하는 연산은 10을 곱하여 자릿수를 늘려준 다음 1을 더해주었습니다. A가 B보다 적은 수이기 때문에 기저조건은 A가 B보다 클 때로 정해주었고 A가 B와 같으면 연산 횟수를 출력하고 바로 끝내주었습니다.

 

 구현 코드

package BOJ.Silver;

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 BOJ16953_A_B {
	static long A, B;
	static int cnt;
	static boolean flag;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		A = Long.parseLong(st.nextToken());
		B = Long.parseLong(st.nextToken());
		queue = new LinkedList<>();
		queue.offer(A);
		bfs(A, B, 1);
		System.out.println(-1);
	}
	
	static void bfs(long a, long b, int cnt) {
		if (a>b) return;
		else if (a==b) {
			System.out.println(cnt);
			System.exit(0);
		}
		
		bfs(a*2, b, cnt+1);
		bfs(a*10+1, b, cnt+1);
	}
}

 

정답!