[백준] 문제번호 1463 (1로 만들기)(java)

<문제 1463 - 1로 만들기>

[문제]

 

[답안]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) { // Tabulation 이용
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n + 1]; // 값을 담을 table 만들기(DP용 메모리)

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1; // 1을 빼는 경우

            if (i % 2 == 0) { // 만약 i가 2로 나누어 떨어지면?
                dp[i] = Math.min(dp[i], dp[i / 2] + 1); //
            }
            if (i % 3 == 0) { // 만약 i가 3으로 나누어 떨어지면?
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }

        }
        System.out.println(dp[n]);
        sc.close();
    }
}

- Dynamic Programming - Tabulation 사용