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

백준 온라인 저지 1463번 - 1로 만들기

Java 알고리즘 문제풀이

풀이

다이나믹 프로그래밍(DP) 문제이다.

간략하게 DP를 소개하자면 큰 문제를 작은 단위로 쪼갠 작은 문제로 큰 문제의 답을 구하는 것을 뜻한다.

푸는 방식에는 2가지가 존재한다. 이 문제도 2가지 방법으로 풀어볼 것이다.

1. Top-Down

2. Bottom-Up

먼저, Top-down은 용어 그대로 위에서부터 아래로 이어지는 것이다.

이 방법에 특징은 재귀함수를 사용하는 것이다. 작은 부분의 답을 저장해 이미 계산을 진행한 작은문제는 저장된 값을 이용하는 방법이다.

/* Top down */
import java.util.Scanner;

public class Beak1463 {
    static int[] d;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        d = new int[n + 1];

        System.out.println(dp(n));
        sc.close();
    }

    private static int dp(int n) {
        if (n == 1)
            return 0;
        if (d[n] > 0)
            return d[n];
        d[n] = dp(n - 1) + 1;
        if (n % 2 == 0) {
            int tmp = dp(n / 2) + 1;
            if (d[n] > tmp)
                d[n] = tmp;
        }
        if (n % 3 == 0) {
            int tmp = dp(n / 3) + 1;
            if (d[n] > tmp)
                d[n] = tmp;
        }
        return d[n];
    }
}

두 번째로 Bottom-up방식의 풀이이다.

먼저, 제일 작은 문제부터 차례대로 풀면서 정답을 구해나가는 방법이다.

이 문제에서는 0일때부터 시작해서 입력한 값의 답을 찾을때까지 무한루프를 도는 방식이다.

/* Bottom Up */
import java.util.Scanner;

public class Beak1463 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int dp[] = new int[n + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i % 2 == 0)
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            if (i % 3 == 0)
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
        }
        System.out.println(dp[n]);
        sc.close();
    }
}