[자바]백준 정수 a를 k로 만들기 [탐색] [엄탱]

문제

입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다. 정수 A를 변경할 때 사용할 수 있는 연산 종류는 다음과 같다.

• 연산 1: 정수 A에 1을 더한다.
• 연산 2: 정수 A에 2를 곱한다.

정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하자.

입력

첫 번째 줄에 양의 정수 A와 K가 빈칸을 사이에 두고 순서대로 주어진다.

출력

첫 번째 줄에 양의 정수 A를 양의 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력한다.

제한

1 ≤ A < K ≤ 1,000,000

예제

문제 설명

정수 A를 +1 혹은 *2를 연산을 해서 K가 되기 위해 최소 연산 횟수를 출력하는 것이다.

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 그리디 알고리즘
• 그래프 탐색
• 너비 우선 탐색

해설

알고리즘 분류를 보면 알 수 있듯이 다이나믹 프로그래밍, 그리디, 탐색 알고리즘으로 문제를 풀 수 있다.

나는 현재 탐색을 공부중이라 탐색에 관련해서 해설을 쓰고 코드는 다이나믹 프로그래밍과 탐색 코드를 기록하겠다.

그리고 시간초과가 발생한 완전 탐색 코드도 기록하겠다.

 

알고리즘 분류에 너비 우선 탐색만 되어 있다.

이유는 너비의 기준을 정수 A의 근처 수로 하는게 아니라 작은 연산 횟수 기준으로 해야하기 때문이다.

연산 횟수를 작은 것부터 탐색해야 하는 이유는 최소 연산 횟수를 답으로 출력해야 하기 때문에 연산 횟수가 작은것 부터 k가 되는지 확인하기 위함이다.

 

기존 BFS가 사용하는 큐대신 우선순위 큐를 준비해야 한다.

• 큐에 넣은 값을 가져온다.
• 가져온 값에 1만큼 증가시키고 count를 1 증가시켜서 우선순위 큐에 넣는다.
• 가져온 값에 2를 곱하고 count를 1 증가 시켜서 우선순위 큐에 넣는다.
• 반복하여 처음 K가 되는 count를 출력한다.

비슷한 알고리즘으로 0-1 너비 우선탐색 알고리즘이 있다.

비슷한 문제 링크

https://tang25.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EB%B0%B1%EC%A4%80-13549%EB%B2%88-%EC%9E%90%EB%B0%94

[자바]백준 13549번 숨바꼭질3 [그래프-다익스트라][엄탱]

dfs를 이용한 코드

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

public class Main {
    static int A; // 시작 수
    static int K; // 목표 수
    static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        A = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        System.out.println(calcMinCountDfs());
        
        br.close();
    }
    
    public static int calcMinCountDfs() {
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[1] - y[1]);
        boolean[] visited = new boolean[K + 1];
        pq.offer(new int[]{A, 0});
        
        while(!pq.isEmpty()) {
            int[] cur = pq.poll();
            
            int a = cur[0];
            int curCount = cur[1];
            
            if (a > K || visited[a]) {
                continue;
            }
            
            if (a == K) {
                return curCount;
            }
            
            visited[a] = true;
            
            pq.offer(new int[]{a * 2, curCount + 1});
            pq.offer(new int[]{a + 1, curCount + 1});
        }
        
        return 0;
    }
}

다이나믹 프로그래밍 기법을 이용한 코드

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

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 K = Integer.parseInt(st.nextToken());

        int[] dp = new int[K + 1];

        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[A] = 0;

        for (int i = A; i < K; i++) {
            if (i + 1 <= K) {
                dp[i + 1] = Math.min(dp[i + 1], dp[i] + 1);
            }

            if (i * 2 <= K) {
                dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);
            }
        }

        System.out.println(dp[K]);
        br.close();
    }
}

시간초과난 dfs탐색 코드

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

public class Main {
    static int A; // 시작 수
    static int K; // 목표 수
    static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        A = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        dfs(A, 0);
        
        System.out.println(answer);
        
        br.close();
    }
    
    public static void dfs(int start, int count) {
        if (start == K) {
            answer = Math.min(answer, count);
            return;
        }
        
        if (start > K) {
            return;
        }
        
        dfs(start * 2, count + 1);
        dfs(start + 1, count + 1);
    }
}