백준 1463번(Java)

import java.io.*;

public class Main {

	static Integer[] 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 Integer[N+1];
		dp[0] = dp[1] = 0;
		
		System.out.println(cal(N));
	}
	
	static int cal(int n) {
		if(dp[n] == null) {
			// 2,3으로 나누어지는 경우
			if(n%6 == 0) {
				dp[n] = Math.min(cal(n-1), Math.min(cal(n/3), cal(n/2))) + 1;
			} 
			// 3으로만 나누어지는 경우
			else if(n%3 == 0) {
				dp[n] = Math.min(cal(n/3), cal(n-1)) + 1;
			}
			// 2로만 나누어지는 경우
			else if(n%2 == 0) {
				dp[n] = Math.min(cal(n/2), cal(n-1))+1;
			} 
			// 2,3으로 둘 다 나누어지지 않는 경우
			else {
				dp[n] = cal(n-1) + 1;
			}
		}
		
		return dp[n];
	}
}