<BOJ>1463번: 1로 만들기

문제

1463번: 1로 만들기

접근

• 문제에 제시된 3가지 연산 조건을 토대로 점화식을 짜면 된다.
  dp[i] = dp[i-1] + 1
  dp[i] = dp[i/2] + 1 (i % 2 == 0)
  dp[i] = dp[i/3] + 1 (i % 3 == 0)
• 위 점화식을 토대로 연산 횟수의 최솟값을 도출해야 한다.

내 코드

import java.io.*;

public class Main {
    static int[] dp = new int[1000005];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + 1;
            if (i % 2 == 0) dp[i] = Math.min(dp[i/2]+1, dp[i]);
            if (i % 3 == 0) dp[i] = Math.min(dp[i/3]+1, dp[i]);
        }
        System.out.println(dp[n]);
    }
}