백준[JAVA] 1463.1로 만들기 - 자바

📖 문제

📃 코드

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

public class Main {
    static Integer[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int X = Integer.parseInt(br.readLine());
        dp = new Integer[X + 1];
        dp[0] = dp[1] = 0;

        System.out.println(recur(X));
    }

    private static int recur(int x) {
        if (dp[x] == null) {
            if (x % 6 == 0) {
                // compare x/3 with x/2 and compare x-1
                // last +1 process is cnt++
                dp[x] = Math.min(Math.min(recur(x / 3), recur(x / 2)), recur(x - 1)) +1;
            } else if (x % 3 == 0) {
                dp[x] = Math.min(recur(x / 3), recur(x - 1)) +1;
            } else if (x % 2 == 0) {
                dp[x] = Math.min(recur(x / 2), recur(x - 1)) +1;
            } else {
                dp[x] = recur(x - 1) +1;
            }
        }
        return dp[x];
    }
}

 

🔗 링크

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

1463번: 1로 만들기