[BOJ] 백준 16953번 : A -> B (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/16953

16953번: A → B

문제

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

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

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

풀이

처음에는 BFS로 생각하고, A에서 B로 두 가지 연산을 계속 실시해서 최소의 경우로 B를 도달하는 횟수는 몇 번인지 판단하는 로직을 세웠었습니다. 하지만, B가 10^9로 꽤 큰 값이었고 결국 메모리 초과를 피할 수 없었습니다.

그래서 이것을 반대로 생각해 보았습니다. A에서 B로 만드는 것이 아닌, B에서 A로 만드는 로직이었죠. 전반적인 로직은 다음과 같습니다.

1. B가 2로 나누어 떨어지지 않거나, 맨 끝자리가 1이 아니라면 A로 만드는 것이 불가능하다.

2. B가 2로 나누어 떨어진다면, B를 2로 나눈다.

3. B의 맨 끝자리가 1이라면, 1을 없앤다.

4. 2, 3번 과정이 성립할 때마다 횟수를 1개씩 올리고, 중간에 성립하지 않는 경우가 생기면 반복문을 종료한다.

자세한 소스코드는 아래와 같습니다.

소스 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
 
        int ans = 1;
        while (B != A) {
            if (B < A) {
                ans = -1;
                break;
            }
 
            String str = String.valueOf(B);
 
            // 맨 끝자리가 1이거나 B가 2로 나누어 떨어지지 않는다면, A로 만들 수 없다.
            if (str.charAt(str.length() - 1) != '1' && B % 2 != 0) {
                ans = -1;
                break;
            }
 
            if (B % 2 == 0) { // B가 2로 나누어 떨어진다면, 2로 나눈다.
                B >>= 1;
            } else { // 그렇지 않고, 맨 끝자리가 1이라면 1을 없앤다.
                str = str.substring(0, str.length() - 1);
                B = Long.parseLong(str);
            }
 
            ans++; // 횟수 증가.
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}
 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.