[Java] 백준 16953번 : A -> B

1. 문제

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

16953번: A → B

 

 

2. 풀이 과정

처음엔 A -> B로 BFS를 사용해서 풀었었고,

나중에 다른 코드를 참고한 후에 B -> A로 갈 수 있는지 확인해가는 방식으로 풀게 됐다.

 

먼저 마지막이 1로 끝나는 수는 홀수 중에 하나이므로 연산을 홀수일 때, 짝수일 때로 나눠볼 수 있다.

짝수면 /2를 하고, 홀수 중에 1로 끝나면 /10을 한다.

둘 다 해당하지 않는 수는 만들 수 없는 수로 끝내면 된다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        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 result = 1;

        while(A < B){
            if(B%2==0){//짝
                B/=2;
            }
            else{//홀
                if(B%10==1){
                    B/=10;
                }
                else{
                    break;
                }
            }
            result++;
        }

        if(A!=B){
            System.out.println(-1);
        }
        else{
            System.out.println(result);
        }

    }
}

 

 

결과