백준 16953번 : A -> B (Java)

🔗 문제 링크

16953번: A → B

---

📖 풀이 과정

 

- 재귀를 이용한 구현 문제입니다.
  - 재귀를 이용하지 않더라도 단순 반복문으로도 풀 수 있습니다.
  
- A -> B로 가도 되며, B -> A로 숫자가 줄어들면서 진행해도 됩니다.
  - 저는 A -> B의 방향으로 구현했습니다.
  
- 연산은 두가지 입니다.
  - 2를 곱하는 경우
  - 숫자의 마지막에 문자 1을 붙이는 경우
  
- 두가지 과정에 대한 재귀 메소드를 구현한 후, A가 B보다 커지는 경우에는 메소드 종료를, A == B인 경우에는 그때까지의 count 값을 담습ㄴ디ㅏ.
  - 문제에서 답을 반환할 때 1을 더한 값을 반환하라고 제시되어있기 때문에 저는 count 변수를 1로 초기화했습니다.

- 여기서 주의할 점은 A,B의 타입입니다.
  - 저는 여기서 4,5번 틀렸습니다. 저와 같은 잘못을 한 분이 계실 수도 있다고 생각해서 추가합니다.
  - 숫자의 범위는 1 이상, 10의 9승 이하입니다. 
  - 즉, int 범위를 넘어 문자열 1을 붙였을 때 int형으로 변환하면서 NumberFormatException이 발생할 수 있습니다.
    - 물론, 이 부분에 대한 예외 처리 코드가 있을 경우에는 int형의 범위를 벗어나지 않게되어 long 타입을 신경안써도 될 것 같습니다.
  - 저는 위 부분에 대한 예외처리 코드를 작성하지 않았기에 타입을 long으로 수정 후 풀었습니다.

 

---

💻 코드

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        int count = 1;
        answer = 0;

        solve(a, b, count);

        if (answer == 0) {
            answer = -1;
        }

        bw.write(String.valueOf(answer));
        bw.flush();

        bw.close();
        br.close();
    }

    private static void solve(long a, long b, int count) {
        if (a == b) {
            answer = count;
            return;
        } else if (a > b) {
            return;
        }
        solve(a * 2, b, count + 1);

        String str = a + "1";
        solve(Long.parseLong(str), b, count + 1);
    }
}