[백준 16953번] A -> B

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

16953번: A → B

 

1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

정수 A와 B가 주어졌을 때 A를 B로 바꿀 수 있는 연산의 최소 횟수를 구하는것.

연산

- 2를 곱한다.

- 1을 수의 가장 오른쪽에 추가한다. 

 

2. 나의 방식대로 문제를 재정의 하자.

연산 방법

- 2를 곱한다. --> 연산결과 : A * 2

- 1을 수의 가장 오른쪽에 추가한다. --> 연산결과 : A*10 + 1

 

A를 B로 만들기 위해서 연산1,2 중 하나를 선택하여 연산했을 때 최소횟수를 구한다. 

 

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

bfs와 그리디 방식으로 문제를 풀 수 있다.

그리디 방식으로는 B로 만들기위해서 A를 증가시키는것이 아니라 B를 감소시키는 방식으로 로직을 짠다.

1. B가 A와 2의배수일 때 (B%2 == 0)  B/=2해줌

2. B의 마지막 숫자가 1이 될때 (B%10 == 1) B/=10해줌

 

bfs 방식으로는 A를 연산시키며 깊이우선 탐색하고, A==B일때의 깊이값을 저장한 후 return한다.

 

 

4. 어떻게 계산할 것인가?

1) 입력

BufferedReader 사용

 

5. 주의할 점은 무엇인가?

입력값의 범위가 1<=A<=B<=10^9이므로 int형으로는 저장할 수 없다. long 사용

 

6. 풀이 과정

1) dfs

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

public class Main {
    static int result = -1;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        long A = Integer.parseInt(st.nextToken());
        long B = Integer.parseInt(st.nextToken());

        dfs(A, B, 0);
        bw.write(result + "\n");

        bw.flush();
        br.close();
        bw.close();
    }
    
    static void dfs(long A, long B, int depth) {
        if (A > B) {
            return;
        }
        if (A == B) {
            result = depth + 1;
            return;
        }
        
        dfs(A*2, B, depth+1);
        dfs(A*10+1, B, depth+1);
        
        return;
    }

}

재귀함수를 사용한다. A*2와 A*10+1연산을 하는 모든 경우를 탐색하고, A==B일때의 깊이값을 전역변수인 result에 저장한다. 그리고 A>B일경우는 더이상 A와 B가 같아질 수 없으므로 저장하지 않고 리턴한다.

 

 

2) 그리디

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

public class Main {
    static int result = -1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        long A = Integer.parseInt(st.nextToken());
        long B = Integer.parseInt(st.nextToken());

        int depth = 0;

        while (A <= B) {
            if (A == B) {
                result = depth+1;
                break;
            }


            if (B % 10 == 1) {
                B /= 10;
            } else if (B % 2 == 0) {
                B /= 2;
            } else {
                result = -1;
                break;
            }

            depth += 1;
        }

        bw.write(result + "\n");

        bw.flush();
        br.close();
        bw.close();
    }

}

 

 

 

 

7. 개선점

그리디 알고리즘 조건을 단순하게 생각해서 설계해야함