백준 25418: 정수 a를 k로 만들기[JAVA]

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

25418번: 정수 a를 k로 만들기

 

 

[난이도]

- Silver 3

 

[알고리즘]

- bfs

 

[코드]

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

public class Main {
    static int A, K, answer = Integer.MAX_VALUE;
    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(), " ");

        A = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        bfs();
    }
    static void bfs() {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{A, 0});
        boolean[] visited = new boolean[K + 1];
        visited[A] = true;
        while (!queue.isEmpty()) {
            int tmp[] = queue.poll();
            if (tmp[0] == K) {
                System.out.println(tmp[1]);
                return;
            }
            // 연산 1과 연산 2를 둘다 시행한다
            if (tmp[0] * 2 <= K) { // 연산 2
                visited[tmp[0] * 2] = true;
                queue.offer(new int[]{tmp[0] * 2, tmp[1] + 1});
            }
            if (!visited[tmp[0] + 1]) { // 연산 1, // 연산 2로 수행한 수가 연산 1보다 더 적은 연산횟수이기 때문에 이미 연산 2로 수행한 수라면 패스
                queue.offer(new int[]{tmp[0] + 1, tmp[1] + 1});
            }
        }
    }
}

 

[풀이]

1. 연산 2와 연산 1을 둘다 시행한다.

2. 연산 2가 가능하다면 연산 2를 시행하고. 연산 후의 숫자를 true로 체크한다.

3. 연산 1은 연산 2로 수행한 수가 연산 1보다 무조건 더 적은 연산횟수를 가지기 때문에 이미 연산 2로 수행한 수라면(!visited[tmp[0])라면 패스

 

제대로 풀이방법이 떠오르지 않았다. 비슷한 문제를 푼적이 있는데 DP로 푸는방법이 훨씬 간단했던것같다.