[code.plus 알고리즘 기초]no. 1463

top-down 방식

package n1463;
 
import java.util.Scanner;
 
public class Main {
    public static int[] dp;//dp[n]은 n을 1로 만드는데 필요한 연산의 최소값
 
    public static int procCnt(int n){
//        System.out.println(n);
//        for(int i = 0; i< dp.length; i++){
//            System.out.print(dp[i]+",");
//        }
        if(n == 1){ // 1이 들어올 때는 연산이 필요없음
            return 0;
        }
        if(dp[n] > 0){ // memorization 어차피 같은 연산이면 연산하지 않도록 하게
            return dp[n];
        }
        dp[n] = procCnt(n-1)+1;
        if(n%2 == 0){
            int temp = procCnt(n/2)+1; // n/2로 해서 리턴 받은 값을 temp에 저장
            if(dp[n] > temp){ //  temp가 dp[n]보다 작다면 dp[n]을 temp로 바꿔준다.
                dp[n] = temp;
            }
        }
        if(n%3 == 0){
            int temp = procCnt(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 X = sc.nextInt();
        dp = new int[X+1];
        System.out.print(procCnt(X));
    }
}
 

bottom-up방식

import java.util.*;
 
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] d = new int[n+1];
        d[1] = 0;
        for (int i=2; i<=n; i++) {
            d[i] = d[i-1] + 1;
            if (i%2 == 0 && d[i] > d[i/2] + 1) {
                d[i] = d[i/2] + 1;
            }
            if (i%3 == 0 && d[i] > d[i/3] + 1) {
                d[i] = d[i/3] + 1;
            }
        }
        System.out.println(d[n]);
    }
}