https://www.acmicpc.net/problem/1463
package boj1463;
import java.io.*;
import java.util.*;
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(recur(N));
}
static int recur(int n){
if(dp[n] == null){
if(n % 6 == 0){
dp[n] = Math.min(recur(n/3),Math.min(recur(n/2),recur(n-1)))+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];
}
}
Integer등 wrapper class 배열의 초기값 : null
int 초기값 : 0
N=10일때
→ 2로 나누어떨어짐 : dp[10] = min(recur(5), recur(9)) + 1
2의 경우 : dp[2] = 1
3의 경우 : dp[3] = 1
→ dp[4] = 2
→ dp[5] = 3
3의 경우 : dp[3] = 1
8의 경우 : dp[8] = min(recur(4), recur(7)) + 1
- 4의 경우 : dp[4] = 2
- 7의 경우 : dp[7] = recur(6) + 1 → dp[4]보다 클수밖에 없으므로 생략
→ dp[8] = 3
→ dp[9] = 2
즉, (3 vs 2) + 1이므로 10 → 9 → 3 → 1로 간 3번이 최소횟수가 됨