백준 자바 문제풀이 #16953

문제 링크

A → B

처음에는 쉽게 접근했다.

B의 일의 자리가 1이냐, B가 2로 나누어 떨어지는가.

주어진 예제도 다 통과했다.

1차시도

package Silver.S2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class S16953 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int count = 1;

        while (b > a) {
            if (b % 10 == 1) {
                b /= 10;
                count++;
            } else if (b % 2 == 0) {
                b /= 2;
                count++;
            }
        }

        if (a > b) {
            System.out.println(-1);
        } else {
            System.out.println(count);
        }
    }
}

그런데 뭔가 영 찜찜해서 조금 더 머리를 굴렸더니

바로 반례가 나왔다.

b가 231이 나오면 231 -> 23이 나오기 때문에

while문에서 탈출하지 못한다.

... 코드를 손봐줬다.

2차시도

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        boolean isPossible = true;
        int count = 1;

        while (b > a) {
            if (b % 10 == 1) {
                b /= 10;
                count++;
            } else {
                if (b % 2 != 0) {
                    isPossible = false;
                    break;
                } else {
                    b /= 2;
                    count++;
                }
            }
        }

        if (isPossible) {
            System.out.println(count);
        } else {
            System.out.println(-1);
        }
    }
}

근데 틀렸단다... 응?

반례 하나를 돌려봤다.

10을 11로 바꾸는게 불가능한데

11 -> 1로 바로 나와버려서

가능한것처럼 출력이 된다.

그래서 아예 a와 b가 같지 않으면 -1을 출력하도록 해줬다.

불필요한 부울변수도 손보는김에 빼줬다.

통과

package Silver.S2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class S16953 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int count = 1;

        while (b > a) {
            if (b % 10 == 1) {
                b /= 10;
                count++;
            } else {
                if (b % 2 != 0) {
                    break;
                } else {
                    b /= 2;
                    count++;
                }
            }
        }

        if (a == b) {
            System.out.println(count);
        } else {
            System.out.println(-1);
        }
    }
}

성공

자바 11 14112 KB 124 ms

무난한 문제였다.

엥...?

... 근데 맞추고 난 다음에 알고리즘 분류를 보니

그래프? BFS라고?

뭔가 싶어서 다른 분들의 풀이를 찾아보니

접근방식에 대한 차이 때문이었다.

문제에서 요구한 방식대로 정직하게 A를 B로 바꾸는 방법은

BFS로 풀이하고 있었다.

나는 B를 A로 바꾸다보니 그냥 그리드 방식으로 풀게된 것이었다.

그리드로 해결한 방법이 메모리나 시간 측면에서 조금 더 좋기는 한데

엄청 차이가 있는건 아니라서

그냥 이렇게도 풀 수 있다는것만 짚고 넘어가려고 한다.