백준 다이나믹 알고리즘 - 1로 만들기 1463 Top-down, Bottom-up 모두 이용(JAVA)

---

문제링크 https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

다이나믹 알고리즘은 top-down 형식(재귀 알고리즘을 사용)과 bottom-up 형식이 있다.

top-down은 위에서 아래로 내려오는 알고리즘 방식으로 메모리제이션을 사용한다. 피보나치 수열을 풀 때 많이 쓰인다.

bottom-up은 for 문을 이용하여 다음 값들을 계산해 나간다.

여기서는 top-down과 bottom-up 형식을 모두 이용하여서 문제를 풀어볼 것이다.

---

Top-Down 형식

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

package dynamic;   import java.util.Scanner;   public class One_1463_topDown {       public static int[] dp;       public static int start(int n) {           //입력 수가 1이면 0을 리턴한다.         if (n == 1) {             return 0;         }                    if (dp[n] > 0) {             return dp[n];         }           //2나 3으로 나눠지지 않으면 n에 1을 빼서 start 함수를 계속한다.         //+1은 횟수를 의         dp[n] = start(n - 1) + 1;           if (n % 2 == 0) {             int temp = start(n / 2) + 1;             if (dp[n] > temp) {                 dp[n] = temp;             }         }         if (n % 3 == 0) {             int temp = start(n / 3) + 1;             if (dp[n] > temp) {                 dp[n] = temp;             }         }           return dp[n];       }       public static void main(String[] args) {           Scanner sc = new Scanner(System.in);           // 입력 받는 수         int n = sc.nextInt();           dp = new int[n + 1];           System.out.println(start(n));     }   }   Colored by Color Scripter

cs

 

Bottom-up 형식

package dynamic;
 
import java.util.Scanner;
 
public class One_1463_bottomUp {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
 
        int[] dp = new int[n + 1];
 
        // 1이 입력되면 0이다.
        dp[1] = 0;
 
        for (int i = 2; i < n + 1; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
                dp[i] = dp[i / 2] + 1;
            }
            if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
                dp[i] = dp[i / 3] + 1;
            }
        }
        System.out.println(dp[n]);
    }
 
}