지난번엔 죽어도 못풀겠더니 생각보다 간단하게 풀었다.
dfs를 통해서 *2를 하거나, 1을 뒤에 붙이는 로직으로 각각 뻗어나가게 했고
m 보다 크거나 같아지면 return 하도록 하였다.값의 범위가 크므로 int가 아니라 long으로 처리할것!
import java.util.*;
public class Main {
static long m;
static long answer = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
m = sc.nextInt();
dfs(n,1);
System.out.println(answer==Integer.MAX_VALUE ? -1 : answer);
}
public static void dfs(long n,long res) {
//System.out.println(n + " "+ res);
if (n >= m) {
if(n==m){
answer = Math.min(res,answer);
}
return;
}
for(int i=0; i<2; i++){
if(i==0){
dfs(n*2,res+1);
}else{
dfs(n*10+1,res+1);
}
}
}
}