[Silver 3] 1463번 1로 만들기

import java.io.*;

public class Main {
    public static int[] dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dp = new int[n+1];
        
        System.out.println(calc(n));
    }
    
    public static int calc(int n) {
        if(dp[n]>0 || n==1) { return dp[n]; }
        
        if(n%6==0) {
            dp[n] = Math.min(calc(n-1), Math.min(calc(n/3), calc(n/2)))+1;
            return dp[n];
        } else if(n%3==0) {
            dp[n] = Math.min(calc(n/3), calc(n-1))+1;
            return dp[n];
        } else if(n%2==0) {
            dp[n] = Math.min(calc(n/2), calc(n-1))+1;
            return dp[n];
        } else {
            dp[n] = calc(n-1)+1;
            return dp[n];
        }
    }
}