백준 1463: 1로 만들기 [Java] -포포

문제

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

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

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

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

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

public class Main {
    static int n;
    static Integer[] dp;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new Integer[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        int result = solve(n);
        System.out.println(result);
    }

    static int solve(int n) {


        if (dp[n] == null) {
            if (n % 3 == 0 && n % 2 == 0) {
                dp[n] = Math.min(solve(n / 3), Math.min(solve(n / 2), solve(n - 1))) + 1;
            } else if (n % 3 == 0) {
                dp[n] = Math.min(solve(n / 3), solve(n - 1)) + 1;
            } else if (n % 2 == 0) {
                dp[n] = Math.min(solve(n / 2), solve(n - 1)) + 1;
            } else {
                dp[n] = solve(n - 1) + 1;
            }
        }

        return dp[n];
    }
}

dp문제로 메모이제이션을 통해 시간제한에 걸리지 않고 해결이 가능하다.
간만에 백준 문제를 포스팅하는데, 이 문제에서 메모이제이션을 할 때 주의할 점을 배웠다.

문제는 쉬운데 낮은 오답률을 보아하니 나와 같은 실수를 많이들 하신 것 같다.

바로, solve() 메소드에서 탐색 순서를

    static int solve(int n) {

        if (dp[n] == null) {
            if (n % 3 == 0 && n % 2 == 0) {
                dp[n] = Math.min(solve(n - 1), Math.min(solve(n / 3), solve(n / 2))) + 1;
            } else if (n % 3 == 0) {
                dp[n] = Math.min(solve(n - 1), solve(n / 3)) + 1;
            } else if (n % 2 == 0) {
                dp[n] = Math.min(solve(n - 1), solve(n / 2)) + 1;
            } else {
                dp[n] = solve(n - 1) + 1;
            }
        }

        return dp[n];
    }

위와 같이 짜면 시간초과가 발생한다.

 같은 로직이어도

Math.min(solve(n-1), solve(n/3));
Math.min(solve(n/3), solve(n-1));

위의 두 줄은 성능에 있어서 차이가 크다.

solve(n-1)부터 탐색을 시작하는 경우는, 1이 될때까지 1씩 감소하며 dp 배열에 값을 기록한다.
하지만 solve(n/3)은 3씩 나누면서 dp에 그 값을 저장하고, 뒤에 solve(n-1) 탐색에서는 solve(n/3)에서 메모이제이션 한 값을 사용할 수 있으므로 속도차이가 나는 것이다.