16953번 - A->B

문제: 

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

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

A를 B로 바꾸는데 필요한 연산의 최 솟값에 1을 더한 값을 출력하라.

 

풀이:

비록 dfs, bfs 과정에 나와있으나, 전혀 쓰지 않는것이 더 좋은 방법이다.

최솟값이라는 말이 잘못된 것이, 하나의 경우밖에 나오지 않는다.

 

이유는 예제 3을 보면 알 것이다.
예제 3의 예시에는 100 → 200 → 2001 → 4002 → 40021 이 나와있다.

100부터 시작하지말고 40021부터 시작해보자.

40021 → 4002 →  2001 →  200 →  100

그렇다면 이때 경우는 

• 2로 나눈다.
• 가장 오른쪽에서 1을 뺀다.

이 두가지이다.

 

2로 나누려면 짝수여야 하며, 1을 오른쪽에서 빼려면 한자리수가 1이여야 한다.

즉, bfs고 dfs고 생각할 것이 없이, 애초에 경우의 수가 1가지라는 소리이다.

B -> A로 진행시키다가 짝수도 아니고, 1도 아닌 순간 -1을 반환하면 된다.

만일 A까지 진행이 된다면 그때 필요한 연산의 최솟값 + 1을 반환하면 된다.

 

아래는 위의 설명에 기반하여 작성된 코드이다.

import java.util.Scanner;

public class AtoB_16953번 {
    static int A, B;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        A = sc.nextInt();
        B = sc.nextInt();

        System.out.println(AtoB(B, 1));
    }

    static int AtoB(int num, int count) {
        while (num > A) {
            num = One(num);
            count++;
        }
        if (num == A) {
            return count;
        } else {
            return -1;
        }
    }

    static int One(int num) {
        if (num % 10 == 1) {
            return (num - 1) / 10;
        } else {
            return Two(num);
        }
    }

    static int Two(int num) {
        if (num % 2 == 0) {
            return num / 2;
        }
        return 0;
    }
}

 

만일 bfs를 이용해서 풀었다면... 불필요한 과정들이 추가되어, 시간이 훨씬 오래걸렸을 것이다.

골드 5티어라 하기에는 쉬운문제 같다.