[백준] 1로 만들기 (Java)

https://www.acmicpc.net/problem/1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

• X가 3으로 나누어 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

주의할점

• 무조건 큰 숫자로 나눈다고 해서 연산 횟수가 줄어들지는 않음
• 2와 3으로 나눴을 때 둘 다 나머지가 0인 경우 (6으로 나눴을 때 나머지가 0인 경우)를 체크해야 함
  -> 이 경우 1로 뺐을 때/2로 나눴을 때/3으로 나눴을 때 세 가지 중에서 최솟값이 되는 경우를 체크

코드

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

public class Main {

    static int dp[];
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int answer = Integer.parseInt(br.readLine());
        dp = new int[answer+1];
        recur(answer);
        System.out.println(dp[answer]);
    }

    static int recur(int N) {
        if (dp[N] == 0 && N > 1) {
            // 6으로 나눠지는 경우
            if (N % 6 == 0) {
                dp[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 1;
            }
            // 3으로만 나눠지는 경우
            else if (N % 3 == 0) {
                dp[N] = Math.min(recur(N / 3), recur(N - 1)) + 1;
            }
            // 2로만 나눠지는 경우
            else if (N % 2 == 0) {
                dp[N] = Math.min(recur(N / 2), recur(N - 1)) + 1;
            }
            // 2와 3으로 나누어지지 않는 경우
            else {
                dp[N] = recur(N - 1) + 1;
            }
        }
        return dp[N];
    }
}