[백준(JAVA)] 1463번: 1로 만들기

문제

✔ 난이도 - Silver 3

설명

사용할 수 있는 연산의 갯수가 최대 3개이다보니 분명히 중복되는 계산이 존재할 것이다. 또한, 문제의 최적해가 작은 문제의 최적해로 구성되어있다. (N이 10일때의 루트는 10 -> 9 -> 3 -> 1 인데 이때 각각 9와 3 또한 각각의 최소 루트를 타고 있다)
따라서, DP(Dynamic Programming 기법을 사용하여 풀면 된다
https://velog.io/@seha01130/동적계획법DP-Dynamic-Programming-정리

풀이 (시간초과)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        int[] memo = new int[N + 1];
        Arrays.fill(memo, -1);

        int result = getCount(memo, N);

        System.out.println(result);

    }

    public static int getCount(int[] memo, int n){
        if (n == 1){
            return 0;
        }
        if (memo[n] != -1){
            return memo[n];
        }

        int count = getCount(memo, n-1) + 1;

        if (n % 3 == 0){
            count = Math.min(getCount(memo, n/3) + 1, count);
        }

        if (n % 2 == 0){
            count = Math.min(getCount(memo, n/2) + 1, count);
        }

        memo[n] = count;
        return memo[n];
    }
}

Top-down 방식의 재귀 + memoization 기법으로 풀었다.
이론적으로는 O(N)에 가까운 동작을 하지만, 재귀 호출 깊이가 깊어지면서 너무 많은 재귀 호출을 하기 때문에 시간초과가 발생하였다.

---

따라서 아래와 같이 bottom-up 방식의 반복문을 사용하여 풀었다.

풀이

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        int[] dp = new int[N + 1];
        
        dp[1] = 0;

        for (int i = 2; i <= N; i++){
            dp[i] = dp[i-1]+1;
            if (i % 3 == 0){
                dp[i] = Math.min(dp[i/3] + 1, dp[i]);
            }
            if (i % 2 == 0){
                dp[i] = Math.min(dp[i/2] + 1, dp[i]);
            }
        }

        System.out.println(dp[N]);
    }
}

TIL💡

📌 https://velog.io/@seha01130/동적계획법DP-Dynamic-Programming-정리
언제 top-down을 사용하고 언제 bottom-up을 사용할지는 아직도 잘 모르겠다.. 경험이 쌓여야 할 것 같은데 위의 포스트에 적어놓은 것처럼 모든 상태를 계산해야하는지, 문제의 크기가 어느정도로 큰지에 따라 우선 구분해야할 것 같다. 근데 보통은 bottom-up 방식이 더 좋은 것 같기도 하고... 아직은 어렵다.