[백준 알고리즘] 16935번 자바(Java) A → B

조건

문제

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

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

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

 

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

 

풀이

처음에 생각했던 방식은 DP(다이나믹 프로그래밍)이었다.
하지만 메모리를 생각했을때 10억이란 숫자는 512MB(1MB당 약 25만개의 정수 담을수있음)이상이 필요하고 그러면 제한조건에 걸리게 된다. 

따라서 방법을 변경해야하는데 생각해낸게 BFS이다.

주어진 수가 1만개이고 BFS는 시간복잡도가 O(log n)이기 때문에 제한시간안에 들어오고도 남는다.

BFS의 방식은 아래 그림과 같다.

 

BFS를 활용해서 목표 수에 도달하는 과정

 

처음 풀었을때는 틀렸는데 이유는 수가 정수형 최대를 초과해서이다. 주어진 수가 10^9라서

21억을 초과안하는데 왜 문제지 싶었는데 문제는 코드 내에서 수에 x10+1 을 하는 과정에 있어서
21억을 초과해버리는것이다. long을 사용하는 방법도 있지만 간단하게 조건문 추가로 그 부분을

해결했다.(따른 푼 사람들의 코드를 보니 도달해야하는 수부터 시작해서 출발 수로 도착하는 방식으로 한 

사람도 있었다. 그것도 정말 좋은 방법이라 생각)

 

 

예제 입력 예시

2 162

예제 출력 예시

5

2-> 4-> 8-> 81 -> 162

소스코드

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

//16953번 자바 A->B

public class Main {

    static class Node{
        int num;
        int cnt;
        public Node(int num, int cnt){
            this.num = num;
            this.cnt = cnt;
        }
    }

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

        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(startNum, 1));
        int ans = -1;
        while(!queue.isEmpty()){
            Node node = queue.poll();
            int nodeNum = node.num;
            int nodeCnt = node.cnt;
            if(nodeNum == endNum){
                ans = nodeCnt;
                break;
            }
            //2를 곱한값
            if(nodeNum*2<=endNum) queue.add(new Node(nodeNum*2,nodeCnt+1));
            //1을 오른쪽에 추가한 값
            if(nodeNum<=100000000){
                if(nodeNum*10+1<=endNum) queue.add(new Node(nodeNum*10+1,nodeCnt+1));
            }
        }
        System.out.println(ans);
    }
}

 

 

 

 

문제 출처

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

16953번: A → B