[Java] 백준(실버-2) 16953번 - A → B

문제 풀이

---

이번 문제는 너비 우선 탐색인 BFS를 이용해 풀 수도 있지만 A→B가 아닌 B→A로 생각해보면 그리디 알고리즘을 이용해서도 풀 수 있는 문제이다.

아이디어 도출

처음에는 단순히 BFS를 이용해, A에서 B가 되기 위해 2가지 연산을 반복하여 최소의 연산횟수로 B가 될 수 있는지를 구하는 로직을 세웠지만, 이것을 반대로 생각하여 B에서 A로 바꾸는 로직을 통해 보다 쉽게 풀 수 있었다.

B에서 A로 바꾸는 아이디어는 다음과 같다.

1. B가 2로 나누어 떨어지지 않거나, 맨 끝자리가 1이 아니라면 A로 만들 수 없기에 반복문을 종료한다.
2. B가 2로 나누어 떨어진다면, B를 2로 나눈다.
3. B의 맨 끝자리가 1이라면, 1을 없앤다.
4. 2, 3번 과정이 성립할 때마다 연산횟수 카운트를 1개씩 증가시키고, A가 B와 같아지면 반복문을 종료한다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;
import java.util.*;

class Main {    

    public static void main(String[] args) throws IOException {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {

                StringTokenizer st = new StringTokenizer(br.readLine());
                int A = Integer.parseInt(st.nextToken());
                int B = Integer.parseInt(st.nextToken());
                
                // 연산횟수는 1부터 시작한다.
                int result = 1;

                while(A != B) {
                    // B가 A보다 작다면 A를 B로 바꿀 수 없다.
                    if(B < A) {
                        result = -1;
                        break;
                    }
                    /**
                     * B가 2로 나누어 떨어진다면, B를 2로 나눈다.
                     * B의 끝자리가 1이라면, 1을 없앤다.
                     * B가 2로 나누어 떨어지지 않거나, 끝 자리 수가 1이 아니라면 A를 B로 바꿀 수 없기에 순회를 종료한다.
                     */
                    if(B % 2 == 0) {
                        B /= 2;
                    } else if(B % 10 == 1) {
                        B /= 10;
                    } else {
                        result = -1;
                        break;
                    }
                    // 연산 횟수를 1 증가시킨다.
                    result++;
                }
                bw.write(result+"\n");       
        }
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.