1로 만들기2

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

풀이

예전에 풀었던 1로 만들기 문제에서 약간의 조건이 추가된 문제이다.

1로 만들었을 때 그 경로를 출력하는 문제인데 1로 만드는 연산 회수를 구하는 것은 dp로 구할 수 있다.

그렇지만 경로를 구하는 것은 별개의 문제였다.

처음에는 그래서 X에 대해서 X-1, X/2 등을 그래프에 저장하였고 이 후 그래프 탐색을 통해 경로를 구했다.

이렇게 하면 문제가 X가 갈 수 있는 모든 경로를 다 저장하고 탐색해야 하기때문에 메모리 낭비가 심했다. 일단 정답은 구하는 것에 성공했지만 메모리 낭비가 신경쓰여 다른 방법을 생각해봤다.

다른 사람의 답안도 참고하여 내 코드와 비교를 해보니 굳이 지나왔던 경로를 그래프 형태로 구현을 안 해도 된다는 것이다.

배열을 하나 더 만들어 dp[i]값이 갱신될 때마다 경로를 저장하고 이후 답을 구했을 때 경로를 출력해주면 된다.

이렇게 푸니 메모리를 적게 사용하고 그래프 탐색도 안하기 때문에 시간도 적게 걸렸다.

아직 많은 공부와 더 효율적인 방법을 찾는 기술을 연습해야한다.

코드 1

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

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

        int n = Integer.parseInt(br.readLine());
        ArrayList<Integer>[] graph = new ArrayList[n + 1];

        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        dp[1] = 0;
        if(n > 1) {
            dp[2] = 1;
            graph[2].add(1);
        }
        if(n > 2) {
            dp[3] = 1;
            graph[3].add(1);
        }


        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            graph[i].add(i - 1);
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i / 2] + 1, dp[i]);
                graph[i].add(i / 2);
            }
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i / 3] + 1, dp[i]);
                graph[i].add(i / 3);
            }
        }

        int ans = dp[n];

        bw.write(ans + "\n");
        ArrayList<Integer> ansList = bfs(n, ans, graph);
        if (ansList != null) {
            for (int a : ansList)
                bw.write(a + " ");
        }
        else
            bw.write(n + "\n");
        br.close();
        bw.close();
    }

    private static ArrayList<Integer> bfs(int start, int count, ArrayList<Integer>[] graph) {
        Queue<Pair> queue = new LinkedList<>();
        boolean[] visit = new boolean[start + 1];
        visit[start] = true;
        for (int a : graph[start]) {
            Pair p = new Pair(a, 1);
            p.record.add(start);
            queue.offer(p);
        }

        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            int i = p.num;
            int cnt = p.cnt;
            visit[i] = true;
            p.record.add(i);
            if (i == 1 && cnt == count) {
                return p.record;
            }
            for (int a : graph[i]) {
                if(!visit[a]) {
                    Pair pair = new Pair(a, cnt + 1);
                    pair.record = new ArrayList<>(p.record);
                    queue.offer(pair);
                }
            }
        }
        return null;
    }
}

class Pair {
    int num;
    int cnt;
    ArrayList<Integer> record;

    public Pair(int num, int cnt) {
        this.num = num;
        this.cnt = cnt;
        record = new ArrayList<>();
    }

    @Override
    public String toString() {
        return "Pair{" +
                "num=" + num +
                ", cnt=" + cnt +
                '}';
    }
}

코드 2

import java.io.*;

public class Main {

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

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

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

        int[] num = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            num[i] = i - 1;
            if (i % 2 == 0) {
                if (dp[i / 2] < dp[i]) {
                    dp[i] = dp[i / 2] + 1;
                    num[i] = i / 2;
                }
            }
            if (i % 3 == 0) {
                if (dp[i / 3] < dp[i]) {
                    dp[i] = dp[i / 3] + 1;
                    num[i] = i / 3;
                }
            }
        }

        int ans = dp[n];

        bw.write(ans + "\n");
        while (true) {
            bw.write(n + " ");
            n = num[n];
            if(n == 0)
                break;
        }
        br.close();
        bw.close();
    }
}