백준 16953 - A - > B

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

16953번: A → B

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

 

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

 

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

 

예제 

2 162

예제 출력

5

---

풀이방법

이 문제는 문제 풀이 방법은 쉽게 떠오르지만, 코드를 짜기는 어려운...그런 문제 중 하나였다.

특히 다른 부분보다 값을 만들 수 없는 경우에 -1 을 출력한다. 라는 부분을 어떻게 코드로 구현할까에 대해서 많이 고민했던 것 같다.

 

이 문제는 크게 3가지로 생각한다.

 

1. A -> B 연산하기 => 숫자 A 에 2를 곱하는 경우와 숫자 A 의 가장 오른쪽에 1을 추가하는 경우

- 2를 곱하는 경우는 사실 아주 쉽고, 오른쪽에 1을 추가하는 경우가 살짝 고민을 해야하는 편에 속한다. 나는 오른쪽에 1을 추가하는 부분을 현재 값 *10 +1 연산을 하는 것으로 대체하였다. 결국 오른쪽에 1을 추가한다는 것은 현재 값이 얼마이던 상관없이 현재 값의 일의 자리가 1 이 된다는 것이고 이에 따라서 현재값*10+1 을 한다.

 

 

2. 연산 도중 A 가 B 를 넘거나 A 가 B 와 같아지는 경우

연산 중 A 가 B 를 초과하는 경우는 뭘 해도 결국 B 에 도달 할 수 없음으로 현재의 result 값을 return 한다. 만약 A와 B 가 동일한 경우 cnt 가 얼마인지 계산하고, 해당 값과 현재 result 의 값을 비교해서 더 작은 숫자를 result 에 담는다.

 

3. A 가 B 에 도달 할 수 없는 경우

A 가 B 에 도달 할 수 있는지 여부를 판단하기 위해서 flag 를 쓰는 방법과 나처럼 result 값이 변화가 있는지 확인하는 방법 2가지로 나눌 수 있을 것 같다.

나는 result 를 Integer.MIN_VALUE 로 지정해두고(integer 타입의 최솟값) 이 값이 변화가 있는지 확인하였다. 만약 findNumber 이 돌면서 값이 계산되었을 때 결국 result 의 값이 변화가 없다면 단 한번도 A 가 B 에 도달하지 못한 것이고 따라서 result 값은 그대로 일 것이다. 이러한 경우 -1 이 출력되도록 하였다.

package baekJoon;

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

public class Quiz_16953_풀이완료 {
    static long a, b; // int 타입으로 설정하면 틀림!! => 문제가 int 가 아닌 long 으로 받기 때문인듯?
    static int result = Integer.MAX_VALUE; // 결과값 -> 처음은 최대값

    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()); // 입력

        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

        // 만약 아래 dfs 메서드가 돌고 끝난 후 result 를 출력하는데
        // 이때 result 가 변화가 없이 처음과 동일한 Integer.Max_val 이라면 -1 출력
        // 아니라면 현재 result+1 출력
        if( findNumber(a, 0) == Integer.MAX_VALUE){
            bw.append("-1");
        }else{
            bw.write((result+1)+"\n");
        }
        bw.flush();
        bw.close();
    }

    // sum 을 기준으로 dfs 가 돌기 시작
    // 만약 sum 이 b 보다 커지면 그냥 result 를 return => b 보다 커졌다라는건 b 에 도달할 수 없다는 의미임으로 그냥 패스하기위해
    // 변화가 없는 result 를 그대로 출력
    // 만약 sum 이 b 와 동일하다면 즉 a 가 b 가 될 수 있다면 a 가 b 로 바뀔때마다 cnt 값을 계산한 후
    // result 와 cnt 값을 비교해서 더 작은 최소값을 result 에 담음

    // else 구문은 sum 에서 2 를 곱하거나
    // sum 에서 10 을 곱하고 1을 더하는 연산을 함
    // ==> 맨 뒤에 1을 추가한다는 건 결국 현재 있는 값이 10의 자리의 수가 된다는 것이고,
    // 그 후 1의 자리에 1이 들어간다는 의미임으로 sum*10+1
    static int findNumber(long sum, int cnt){
        if (sum > b) {
            return result;
        }
        if (sum == b) {
            result = Math.min(result, cnt);
//            System.out.println("result : " + result);

        } else{
            findNumber(sum * 2, cnt+1);
            findNumber(sum * 10 + 1, cnt + 1);
        }

        return result;
    }
}