백준 1463번: 1로 만들기 자바

 

1463번

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
	
	static Integer[] dp;
	
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int num = Integer.parseInt(br.readLine()); 
        br.close();
        
        dp = new Integer[num + 1];
        dp[0] = dp[1] = 0;
        
        System.out.print(recur(num));
        
	}
    
    static int recur(int N) {
        if(N == 1) return 0;
        
		if (dp[N] == null) {
			if (N % 6 == 0) {
				dp[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
			}
			else if (N % 3 == 0) {
				dp[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
            }
			else if (N % 2 == 0) {
				dp[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
			}
			else {
				dp[N] = recur(N - 1) + 1;
			}
		}
		return dp[N];
	} 
	
}