[백준] 1463번 1로 만들기 _ JAVA ( 주석 설명 )

1번 

→ Top-down 방식

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


public class Main {
    static Integer[] dp; //각 숫자별로 1로 만드는 연산 횟수의 최솟값을 저장한다.
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); //정수 N을 입력한다.
        dp = new Integer[N+1];

        //기본값을 설정해준다.
        //dp[N]!=null이 아니게끔 하는 기본값
        dp[0] = 0;
        dp[1] = 0;
        
        System.out.println(solve(N)); //N을 1로 만드는 연산 횟수의 최솟값을 출력한다.
    }


    private static int solve(int N) {
        if(dp[N]==null) {
            //N을 1로 만드는 연산의 최솟값은
            //2로 나누는 횟수와 3을 나누는 횟수를 비교해서 그 중 작은 값을 택해야 한다.
            //N%2, N%3만큼은 -1을 하는 연산 횟수이며,
            //+1은 각 연산을 할 때마다 그 횟수를 카운팅 하기 위함이다.
            //따라서 위와 같은 점화식을 도출할 수 있다.
            dp[N] = Math.min(solve(N/2) + 1 + N%2 , solve(N/3) + 1 + N%3);
        }
        return dp[N];
    }
}

 

---

 

2번 

→ Bottom-up 방식

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


public class Main {
    static Integer[] dp; //각 숫자별로 1로 만드는 연산 횟수의 최솟값을 저장한다.
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); //정수 N을 입력한다.
        dp = new Integer[N+1];

        //기본값을 설정해준다.
        //dp[N]!=null이 아니게끔 하는 기본값
        dp[0] = 0;
        dp[1] = 0;

        System.out.println(solve2(N)); //N을 1로 만드는 연산 횟수의 최솟값을 출력한다.
    }

    //Bottom-up 방식
    private static int solve2(int N){
        for(int i=2;i<=N;++i){
            dp[i] = Math.min(dp[i/2] + 1 + i%2, dp[i/3] + 1 + i%3);
        }

        return dp[N];
    }
}

 

---

 

3번 

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


public class Main {
    static Integer[] dp; //각 숫자별로 1로 만드는 연산 횟수의 최솟값을 저장한다.
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); //정수 N을 입력한다.
        dp = new Integer[N+1];

        //기본값을 설정해준다.
        //dp[N]!=null이 아니게끔 하는 기본값
        dp[0] = 0;
        dp[1] = 0;

        System.out.println(solve3(N)); //N을 1로 만드는 연산 횟수의 최솟값을 출력한다.
    }
    
    private static int solve3(int N){
        if(dp[N]==null) {
            if (N % 6 == 0) {
                dp[N] = Math.min(solve3(N / 3), Math.min(solve3(N / 2), solve3(N - 1))) + 1;
            } else if (N % 3 == 0) {
                dp[N] = Math.min(solve3(N / 3), solve3(N - 1)) + 1;
            } else if (N % 2 == 0) {
                dp[N] = Math.min(solve3(N / 2), solve3(N - 1)) + 1;
            }
            else{
                dp[N] = solve3(N-1) + 1;
            }
        }

        return dp[N];
    }

}