DP - 백준1463 1로 만들기

풀이
각 index 숫자들의 연산횟수 테이블
* 각 숫자에 해당하는 index에, 그 숫자의 연산 최소 횟수 저장
점화식
n = Min(n-1, n/3, n/2) + 1
* n-1의 연산횟수와, n/3의 연산횟수와, n/2의 연산횟수중 가장 적은 횟수
* 연산 횟수를 +1 더해주는 것

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Integer.parseInt(br.readLine());
        //점화식
        //n = Min(n-1, if(n%3==0)n/3, if(n%2==0)n/2))+ 1
        //테이블
        int[] table = new int[2000000];
        //초기값
        table[1] = 0;
        table[2] = 1;
        table[3] = 1;
        //테이블채우기
        for(int i = 4; i <= x; i++){
            int min = table[i-1];
            if(i%3 == 0){
                min = Math.min(min, table[i/3]);
            }
            if(i%2 == 0){
                min = Math.min(min, table[i/2]);
            }
            table[i] = min + 1;
        }
        System.out.println(table[x]);
    }
}

* n/3 또는 n/2의 연산횟수와 비교하는 경우, 당연히 n/3 또는 n/2가 존재하는 지 검사