[DP] 백준 1463 1로 만들기 JAVA

package com.test.dynamicProgramming;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class DP_2_1463 {
    public static void main(String[] args) throws Exception{
        // [DP] 1463 1로 만들기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        //DP테이블 : i를 1로 만들 때 연산하는 횟수의 최솟값
        int dp[] = new int[n + 1];

        for (int i = 2 ; i <= n ; i++) {
            dp[i] = dp[i-1] + 1;
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i/2] + 1);
            }
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i/3] + 1);
            }
        }
        System.out.println(dp[n]);
    }
}

시간복잡도 : O(n)