[백준] 16953번 A->B (자바 풀이)

문제

16953번: A → B

풀이

이 문제는 재귀 함수를 이용해 간단하게 해결 할 수 있다. 

 

1. 2를 곱한다 -> A*2 

2. 1을 수의 가장 오른쪽에 추가한다 -> A*10 +1

 

위의 두 연산을 DFS 형태로 재귀적으로 부르면 브루트포스 방식으로 해결 가능하다.

간단하게 풀렸을것 같지만, 처음 시도했을때 틀렸습니다를 받았다.

 

뭐가 문제일까 고민하다가, 변수의 타입을 int로 한게 문제였음을 깨달았다. 

dfs() 함수에서 if(num > B) return; 이라는 코드가 있는데, 만약 num*2를 계속해서 하다가 int의 범위를 벗어나면 

이 부분이 문제가 발생할 수 있다. 따라서 int를 long 타입으로 바꿔주었더니 통과할 수 있었다.

코드

import java.io.*;
import java.util.*;
 
public class Baekjoon_16953 {
    static long A,B, ans;
    static boolean flag;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        A = sc.nextInt();
        B = sc.nextInt();
        dfs(A, 1);
        if(flag) System.out.println(ans);
        else System.out.println(-1);
    }
    
    public static void dfs(long num, int cnt) {
        if(num > B) return;
        if(num == B) {
            ans = cnt;
            flag = true;
            return;
        }
        
        dfs(num*2, cnt+1);
        dfs(num*10+1, cnt+1);
    }
}

결과