[백준] 1463번 - 1로 만들기 [Java]

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

 

[백준] 1463번 - 1로 만들기 [Java]

[백준] 1463번 - 1로 만들기 [Java]

---

1.  아이디어

 

다이나믹 프로그래밍 또는 BFS를 이용해서 해결할 수 있다.

---

2. 문제풀이

 

다이나믹 프로그래밍은 Top-Down, Bottom-Up 그리고 BFS 총 3가지 방식으로 풀었다.

 

Bottom-Up 다이나믹 프로그래밍은 2부터 N까지 각 숫자를 만드는데 필요한 연산의 최솟값을 찾는 방식으로 풀었다.

특정 숫자가 6의 배수라면 해당 숫자는 3으로 나눈 수에서 3을 곱했거나 2로 나눈 수에서 2를 곱했거나 1 작은 수에서 1을 더해서 만들었을 때 연산의 횟수가 최소가 된다.

특정 숫자가 3의 배수라면 해당 숫자는 3으로 나눈 수에서 3을 곱했거나 1 작은 수에서 1을 더해서 만들었을 때 연산의 횟수가 최소가 된다.

특정 숫자가 2의 배수라면 해당 숫자는 2로 나눈 수에서 2를 곱했거나 1 작은 수에서 1을 더해서 만들었을 때 연산의 횟수가 최소가 된다.

특정 숫자가 3의 배수도 2의 배수도 아니라면 해당 숫자는 1 작은 수에서 1을 더해서 만들었을 때 연산의 횟수가 최소가 된다.

 

Top-Down 다이나믹 프로그래밍은 DFS를 통해 N부터 같은 원리로 재귀를 돌리면 되는데 이때 메모이제이션을 위해 HashMap을 활용했다.

 

BFS는 숫자와 연산 횟수를 담은 Node를 탐색하며 1을 찾을 때까지 반복하면 되는데 이때 우선순위 큐를 활용해서 연산 횟수가 가장 적은 Node를 우선으로 탐색하도록 로직을 구현하고 방문 체크를 진행했다.

---

3. 코드

 

import java.io.*;

public class Main_DP {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

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

        for (int i = 2; i <= N; i++) {
            if (i % 6 == 0) dp[i] = Math.min(dp[i - 1], Math.min(dp[i / 3], dp[i / 2])) + 1;
            else if (i % 3 == 0) dp[i] = Math.min(dp[i / 3], dp[i - 1]) + 1;
            else if (i % 2 == 0) dp[i] = Math.min(dp[i / 2], dp[i - 1]) + 1;
            else dp[i] = dp[i - 1] + 1;
        }

        System.out.println(dp[N]);
    }
}

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

public class Main_DP {

    private static final Map<Integer, Integer> dp = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        dp.put(1, 0);

        System.out.println(recur(N));
    }

    private static int recur(int N) {
        if (dp.containsKey(N)) return dp.get(N);

        if (N % 6 == 0) dp.put(N, Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1);
        else if (N % 3 == 0) dp.put(N, Math.min(recur(N / 3), recur(N - 1)) + 1);
        else if (N % 2 == 0) dp.put(N, Math.min(recur(N / 2), recur(N - 1)) + 1);
        else dp.put(N, recur(N - 1) + 1);

        return dp.get(N);
    }

}

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

public class Main_BFS {

    private static class Node implements Comparable<Node> {
        int num;
        int cnt;

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

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.cnt, o.cnt);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        System.out.println(bfs(N));
    }

    private static int bfs(int N) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[1 + N];

        pq.add(new Node(N, 0));
        visited[N] = true;

        while (!pq.isEmpty()) {
            Node item = pq.poll();

            if (item.num == 1) return item.cnt;

            if (item.num % 3 == 0 && !visited[item.num / 3]) {
                pq.offer(new Node(item.num / 3, item.cnt + 1));
                visited[item.num / 3] = true;
            }
            if (item.num % 2 == 0 && !visited[item.num / 2]) {
                pq.offer(new Node(item.num / 2, item.cnt + 1));
                visited[item.num / 2] = true;
            }
            if (!visited[item.num - 1]) {
                pq.offer(new Node(item.num - 1, item.cnt + 1));
                visited[item.num - 1] = true;
            }
        }

        return -1;
    }

}

---

4. 후기

 

- Bottom-Up

- Top-Down

- BFS