[백준] 12852 : 1로 만들기 2

문제 출처 : https://www.acmicpc.net/problem/12852

소요 시간 : 풀이(55m) + 더 좋은 풀이(15m)

---

문제

---

시도 & 풀이

 

일단 DP로 풀었다.

 

package coding.DP3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class bj_12852 {

    static Point[] points;

    public static void main(String[] args) throws IOException {
        int N = read();

        solve(N, 0);
        printResult(N);
    }

    static int read() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());    // N : 1 ~ 1,000,000
        points = new Point[N+1];

        for (int i = 1; i <= N; i++) {
            points[i] = new Point(-1, Integer.MAX_VALUE);
        }

        return N;
    }

    static class Point {
        int index;
        int min;

        public Point(int index, int min) {
            this.index = index;
            this.min = min;
        }
    }

    static void solve(int n, int cnt) {
        if (n == 1) return;

        cnt++;
        if (n%3 == 0 && points[n/3].min > cnt) {
            points[n/3] = new Point(n, cnt);
            solve(n/3, cnt);
        }
        if (n%2 == 0 && points[n/2].min > cnt) {
            points[n/2] = new Point(n, cnt);
            solve(n/2, cnt);
        }
        if (n > 1 && points[n-1].min > cnt) {
            points[n-1] = new Point(n, cnt);
            solve(n-1, cnt);
        }
    }

    static void printResult(int n) {
        if (n == 1) {
            System.out.print("0\n1");
            return;
        }

        // 1st : 최소 연산 횟수
        // 2nd : N을 1로 만드는 방법에 포함된 수
        StringBuilder sb = new StringBuilder();
        sb.append(points[1].min).append("\n");

        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        for (int i = points[1].index; i < n; i = points[i].index) {
            stack.push(i);
        }
        stack.push(n);

        while (!stack.isEmpty()) {
            sb.append(stack.pop()).append(" ");
        }

        System.out.println(sb.toString());
    }
}

 

푸는 건 성공적이었지만 1의 경우를 따로 정리해야 한다는 점이 아쉬워 더 좋은 풀이를 찾았다.

---

더 좋은 풀이

 

내 풀이의 문제점이었던 N이 1인 경우를 한번에 해결할 뿐만 아니라 N을 1로 만드는 방법에 포함되어 있는 수를 연쇄적으로 작성하기 위해 썼던 Stack 자료 구조 또한 사용할 필요가 없었다.

 

package coding.DP3;

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

public class bj_12852_refined {

    static boolean[] visited = new boolean[1000001];

    static class Node {
        int num;
        int depth;
        String process;

        Node(int num, int depth, String process) {
            this.num = num;
            this.depth = depth;
            this.process = process;
        }
    }

    private static void BFS(int N) {
        Queue<Node> q = new LinkedList<Node>();
        q.add(new Node(N, 0, String.valueOf(N)));

        while (!q.isEmpty()) {
            Node top = q.poll();
            int num = top.num;
            int depth = top.depth;
            String process = top.process;

            if (num == 1) {
                System.out.println(depth);
                System.out.println(process);

                return;
            }

            if (num < 1)
                continue;

            if (num % 3 == 0 && !visited[num / 3]) {
                visited[num / 3] = true;
                q.add(new Node(num / 3, depth + 1, process + " " + String.valueOf(num / 3)));
            }
            if (num % 2 == 0 && !visited[num / 2]) {
                visited[num / 2] = true;
                q.add(new Node(num / 2, depth + 1, process + " " + String.valueOf(num / 2)));
            }
            if (!visited[num - 1]) {
                visited[num - 1] = true;
                q.add(new Node(num - 1, depth + 1, process + " " + String.valueOf(num - 1)));
            }

        }
    }

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

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

        br.close();
    }
}

// 풀이 출처 : https://www.acmicpc.net/source/30084894

 

 

상단 : 더 좋은 풀이, 하단 : 기존 풀이

 

확실히 Stack을 제거하고 나니 소요시간도 사용하는 메모리도 훨씬 줄어들었다.

 

---

알게 된 점

 

획기적이네....