백준 - 1로 만들기

 

 

DP 개념이 처음에는 무슨 말인지 이해가 안되었는데, 계속 보다보니 이해가 됐다 , 내가 푼 것은 아니고 

https://st-lab.tistory.com/132 이분의 블로그에 있는 내용을 베껴왔다. 그런데 혼자 풀라고 했으면 절대 못 풀었을 것 같다.

 

원리는 이렇다 , 재귀를 이용해서 계산하게 되면 어마어마한 양의 계산을 수행해야한다.

하지만 이전에 계산했던 내용을 저장해놓고 , 거기서부터 계산을 하게 되면 계산해야 되는 양을 훨씬 줄일 수 있다.

import java.util.Scanner;
public class Main {
 
	static Integer[] dp;
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
 
		int N = in.nextInt();
 
		dp = new Integer[N + 1];
		dp[0] = dp[1] = 0;
 
		System.out.print(recur(N));
 
	}
 
	static int recur(int N) {
 
		if (dp[N] == null) {
			// 6으로 나눠지는 경우 
			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];
	}
 
}