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

오랜만에 코테 공부를 시작하니까
다 했던거고, 그리 어렵지 않은 문제인데도 풀지 못했다😢
지금 부터 차근 차근히 다시 공부하면 될 거다!
DP의 기본 수준의 문제를 보며 다시금 되새겨 보자💪🏻

📍 문제

정수 N을 1로 만들기 위한 연산 횟수의 최솟값은?

• 연산 종류

1. 3으로 나누기
2. 2로 나누기
3. 1 빼기

💡 접근

지금 구하고자 하는 것은 바로 연산 횟수의 최솟값이다.
여기서 생각 해야하는 것은,
X 부터 시작해서 1 까지 빨리 가야한다,
즉, 만약 이전에 이미 해당 값에 대한 도착한 정보가 있다면, 그 값이 최솟값이라는 것이다.

결과적으로,

연산 횟수의 최솟값을 저장하는 dp[]를 사용하면,
최솟값을 구할 수 있음과 동시에, 중복된 연산을 피할 수 있다.

✏️ 해결

dp배열을 활용하여, 이미 구한 최솟값의 연산은 하지않는다.
연산이 가능한 케이스를 나누어 해당 최솟값을 dp배열에 저장한다.
dp배열은 Integer로 선언하여 탐색하지 않은 배열은 null로 구별 가능하다.

import java.io.*;

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[1] = 0;

        System.out.println(find(N));
    }

    private static int find(int n) {
        if (dp[n] == null) {
            if (n % 6 == 0) {
                dp[n] = Math.min(find(n / 3), Math.min(find(n / 2), find(n - 1))) + 1;
            } else if (n % 3 == 0) {
                dp[n] = Math.min(find(n / 3), find(n - 1)) + 1;
            } else if (n % 2 == 0) {
                dp[n] = Math.min(find(n / 2), find(n - 1)) + 1;
            } else {
                dp[n] = find(n - 1) + 1;
            }
        }
        return dp[n];
    }
}