[백준 / DP] 1463 : 1로 만들기 (Java)

<정답>

import java.io.*;
import java.lang.Math;

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

최솟값 구하는 게 함정이었다. 막 구해도 되는 줄 알았는데

 

아래는 재귀방식으로 푼 코드다. 시간초과로 돌아가진 않는다. vs code에서 동작시키니 값은 똑같이 나온다.

import java.io.*;
import java.lang.Math;

class Main{
    static int[] 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 int[n+1];

        System.out.print(recur(n));
    }
    static int recur(int n){
        if(n == 1)
            return 0;
        if(dp[n] > 0)
            return dp[n];
        dp[n] = recur(n-1) + 1;
        if(n%2==0){
             dp[n] = Math.min(dp[n], recur(n/2)+1);
        }
        if(n%3==0){
            dp[n] = Math.min(dp[n], recur(n/3)+1);
        }
        return dp[n];
    }
}