BOJ[JAVA]_ 12852 1로 만들기2

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

12852번: 1로 만들기 2

 

처음 푼 방법은 아래와 같은데 재귀호출로 점화식을 구현했는데, 시간초과 오류가 발생했다.

public class Main {

    static int[] DP;

    static int solution(int x) {
        if (DP[x] != Integer.MAX_VALUE) return DP[x];
        if (x == 1) return DP[x] = 0;
        // x가 1 이면 답은 0 이다.
        int r2 = Integer.MAX_VALUE, r3  = Integer.MAX_VALUE;
        int r1 = 1 + solution(x - 1);
        // x에서 1을 뺀 (x-1) 수의 답 +1 회를 구한다
        if (x % 3 == 0) r3 = 1 + solution(x / 3);
        // x에서 3을 나눈 x/3 수의 답 +1 회를 구한다.
        if (x % 2 == 0) r2 = 1 + solution(x / 2);
        // x에서 2를 나눈 x/2 수의 답 +1 회를 구한다.
        return DP[x] = Math.min(r1, Math.min(r2, r3));
        // 최소값을 리턴한다
    }

    static void print(int x) {
        if (x == 1) {
            System.out.println(1);
            return;
        }
        System.out.print(x + " ");// 현재 숫자 x를 출력한다
        
        // 다음 숫자 y를 찾는다
        // 다음 숫자 y는, x-1, x/3, x/2 셋 중 하나이다.
        // 이 셋 중에서 DP값이 가장 작은 수가 y 이다.

        int y = x - 1;
        if (x % 3 == 0 && DP[x / 3] < DP[y]) y = x / 3;
        if (x % 2 == 0 && DP[x / 2] < DP[y]) y = x / 2;
        
        // 다음 숫자 출력 재귀호출
        print(y);
    }

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int x = scanner.nextInt();
            DP = new int[x + 1];
            Arrays.fill(DP, Integer.MAX_VALUE);
            System.out.println(solution(x));
            print(x);
        }
    }
}

 

 

두번째로 푼 방법

점화식을 반복문으로 구현하였더니 시간초과 문제가 해결되었다.

public class Main {

    static int[] DP;

    static void print(int x) {
        if (x == 1) {
            System.out.println(1);
            return;
        }
        System.out.print(x + " ");
        int y = x - 1;
        if (x % 3 == 0 && DP[x / 3] < DP[y]) y = x / 3;
        if (x % 2 == 0 && DP[x / 2] < DP[y]) y = x / 2;
        print(y);
    }

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int x = scanner.nextInt();
            DP = new int[Math.max(4, x + 1)];
            DP[1] = 0;
            DP[2] = DP[3] = 1;
            for (int i = 4; i <= x; ++i) {
                DP[i] = DP[i - 1] + 1;
                if (i % 3 == 0) DP[i] = Math.min(DP[i], DP[i / 3] + 1);
                if (i % 2 == 0) DP[i] = Math.min(DP[i], DP[i / 2] + 1);
            }
            System.out.println(DP[x]);
            print(x);
        }
    }
}