백준 16953번 - A→B

https://www.acmicpc.net/problem/16953

16953번: A → B

[풀이]

​

A와 B의 값이 작다면 DP로 풀 수 있는 문제지만, 값이 크기 때문에 재귀적으로 풀었다.

​

A = A*2 와 A = A * 10 + 1 두 가지로 나눠서 재귀함수를 호출하면서 B와 같아질 때의 카운트를 리턴하도록 한다.

​

재귀함수의 탈출조건은 A가 B보다 커질 경우로 해서 무한 루프에 빠지지 않도록 구현했다.

​

​

[소스코드]

import java.util.Scanner;

public class Main {	//bj16953 A->B
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		long a=sc.nextLong();
		long b=sc.nextLong();
		long min=go(a,b,0);
		if(min==Long.MAX_VALUE) System.out.println(-1);
		else System.out.println(min);
		
	}
	public static long go(long a,long b,long num) {
		else if(a>b) {
			return Long.MAX_VALUE;
		}
		else if(a==b) {
			return 1;
		}
		long min=Long.MAX_VALUE;
		long t1=go(a*2,b,num);
		if(t1!=Long.MAX_VALUE) min=min<t1+1?min:t1+1;
		long t2=go(a*10+1,b,num+1);
		if(t2!=Long.MAX_VALUE) min=min<t2+1?min:t2+1;
		return min;
	}
}