백준 Q16953 A to B

in Algorithm on baekjoon


문제

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

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

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

입출력

  • 입력: 첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.
  • 출력: A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

풀이 A

문제 그대로 A에서 B로 가능 방법이 두 가지이다. A에 2를 곱하거나, A에 1을 가장 오른쪽에 추가한다.
이 중 1을 추가하는 경우라는 말은 수식적으로 표현하면 10A + 1이 될 것이다.
그래서 A로부터 시작하여 2가지 경우의 수를 계속 탐색하다 보면
B에 도달할 수 있거나, 없다면 -1을 출력한다.
도달할 수 없는 경우는 A를 계산하다가 B를 초과한 경우 더 이상 B에 도달할 수 없는 경우가 된다.

  • A_next의 경우의 수: 2A or 10A + 1
  • Result: A_next == B인 경우 최소 횟수 + 1 또는 A_next > B 이면 -1

그러면 A를 기준으로 2가지 경우의 수를 탐색하고, 그 다음 A에서도 2가지 경우의 수를 탐색해주는 방향으로 설계한다면 이런 코드가 될 것이다.

private static long atob(long a, long b, long level){
    long aDouble = a * 2; // 2를 곱한다.
    long aAppend1 = a * 10 + 1; // 1을 수의 가장 오른쪽에 추가한다.

    if(aDouble == b || aAppend1 == b){
        return level + 1; // A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값
    }
    else if(aDouble > b && aAppend1 > b){
        return -1; // 연산된 게 b 이상인 경우 도달 불가, -1로 반환
    }
    else {
        long aDoubleAnswer = atob(aDouble, b , level + 1);
        long aAppend1Answer = atob(aAppend1, b, level + 1);

        // 2가지 연산의 결과 중 최소값 반환
        if (aDoubleAnswer == -1) {
            return aAppend1Answer;
        }
        else if (aAppend1Answer == -1) {
            return aDoubleAnswer;
        }
        return Math.min(aDoubleAnswer, aAppend1Answer);
    }
}

참고로 여기서 주의할 점은 a와 b를 long형으로 했다는 점이다. 여기서 입력을 보면 (1 ≤ A < B ≤ 10^9) 이렇게 범위가 정해져 있다. a에서 b로 가는 과정에서 integer overflow가 될 수 있는 상황이므로 long형으로 바꿔줘서 문제를 해결했다.

풀이 B

자, 그럼 위 문제 해결했다고 땡인가? 아니다. 이 문제의 백미는 ‘생각을 뒤집는 것‘이다.
A에서 B로 가는 방법을 찾는 문제에서 B는 어떻게 A로 부터 왔는가라는 문제로 바꿔보는 것이다.
A에서 B로 갈때 경우의 수는 2A 또는 10A + 1이라 되었다면, B입장에서 생각해본다면,

  • B가 짝수일 때, 이전 과정은 2배 곱해서 온 것이므로, 현재 B에서 2를 나눈게 이전 B 과정
  • B의 일의 자리가 1일 때, 이전 과정은 10배 곱해서 1을 더한 것이므로, 현재 B에서 10을 나눈게 이전 B 과정

이렇게 역전해서 볼 수도 있다는 것이다.

이런식으로 추적하다보면 원하는 A가 나오거나, 나올 수 없는 경우를 볼 수 있을 것이다.
여기서 A가 나올 수 없는 경우는 B를 역추적한 결과가 A 보다 작은 경우일 것이다.

이렇게 B기준으로 생각하면은 아래와 같은 코드로도 짤 수 있다.

private static int btoa(long a, long b, int level){
    while(true){
        // a, b 비교
        if(a == b){
            return level;
        }
        else if(a > b){
            return -1;
        }

        // b기준 계산
        if(b % 10 == 1){ //끝이 1인 경우는 이전단계에서 1을 붙인 경우
            level++;
            b /= 10;
        }
        else if(b % 2 == 0){ // 짝수인 경우는 이전단계에서 2를 곱한 경우
            level++;
            b /= 2;
        }
        else{
            return -1;
        }
    }
}

결론

풀이A와 풀이B를 비교해보면 시간상으론 풀이B가 더 경제적이다.
풀이A 경우 재귀함수를 쓰면서 탐색을 한 것이고,
풀이B 경우 반목문 내에서 찾아가는 과정이라 더 간단하게 짤 수 있었다.

이 문제를 통해 단순히 한가지 방법만 고수하는 스타일이 아닌,
유연한 생각을 가지고 다양하게 관점을 바라볼 필요성이 있다.