[白俊]1463号:1

質問する

問題を解く

コード#コード#

import java.util.Scanner;

public class Main{

    //메모이제이션 할 배열을 정적 필드로 선언한다.
    static Integer[] dp;

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();

        //새로운 배열 선언
        dp = new Integer[num + 1];
        dp[0] = dp[1] = 0;

        System.out.print(recur(num));


    }


    static int recur(int N){

        //초기화전 dp는 null값을 가진다.
        if(dp[N] == null){
            //3과 2 둘 다 나눌 수 있는 경우, 세가지 경우 중 최소값을 선택한다.
            if(N % 6 == 0){
                dp[N] = Math.min(recur(N-1), Math.min(recur(N/3), recur(N/2)))+1;
            }
	    //3으로 나눌 수 있는 경우, 
            else if(N % 3 == 0){
                dp[N] = Math.min(recur(N/3), recur(N-1)) +1;
            }
            //2로 나눌 수 있는 경우,
            else if(N % 2 == 0){
                dp[N] = Math.min(recur(N/2), recur(N-1)) +1;
            }
	    //2와 3로 나눌 수 없는 경우,
            else{
                dp[N] = recur(N-1) +1;
            }

        }
        return dp[N];
    }


}