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

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

 

import java.io.*;
import java.util.*;

public class Main {
    static Integer[] 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 Integer[n+1];
        dp[0] = dp[1] = 0;

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

    static int recur(int n) {
        if(dp[n] == null) {
            // 6으로 나눠지는 경우
            if(n % 6 == 0) {
                dp[n] = Math.min(recur(n-1), Math.min(recur(n/3), recur(n/2))) + 1;
            } 
            // 3으로 나눠지는 경우
            else if (n % 3 == 0) {
                dp[n] = Math.min(recur(n-1), recur(n/3)) + 1;
            } 
            // 2로 나눠지는 경우
            else if (n % 2 == 0) {
                dp[n] = Math.min(recur(n-1), recur(n/2)) + 1;
            } 
            // 그 외의 경우
            else {
                dp[n] = recur(n-1) + 1;
            }
        }
        return dp[n];
    }
}

---

n  = 10일 때

1) else if (n % 2 == 0)  조건에 해당

 

2) recur(9) 재귀함수 실행

n = 9로 재귀함수 실행

==> 3으로 나눠지는 경우에 해당

==> recur(8)과 recur(3) 중 더 작은 return값을 판단

• recur(8)
  • recur(7)
    • recur(6)
      • recur(5)
        • recur(4)
          • recur(3)
            • recur(2)
              • recur(1)
            • recur(1)
          • recur(2)
            • recur(1)
      • recur(2)
        • recur(1)
      • recur(3)
        • recur(2)
          • recur(1)
        • recur(1)
  • recur(4)
    • recur(3)
      • recur(2)
        • recur(1)
    • recur(2)
      • recur(1)
• recur(3)
  • recur(2)
    • recur(1)
  • recur(1)

현재 초기화 된 값이 dp[0]과 dp[1]밖에 없기 때문에, recur(1)에 도달해야 return 값으로 0을 받을 수 있다.

recur(9)에서 recur(1)이 될 때 까지 재귀를 한 결과, recur(9)는 2번만에 recur(1)에 도달하는 것을 확인할 수 있다.

// recur(9)
dp[9] = Math.min(recur(8), recur(3)) + 1;

// recur(8)
dp[8] = Math.min(recur(7), recur(4)) + 1; // ==> Math.min(3, 2) + 1 ==> 2 + 1 ==> 3

// recur(3)
dp[3] = Math.min(recur(2), recur(1)) + 1; // ==> Math.min(1, 0) + 1 ==> 0 + 1 ==> 1

// recur(8)의 return값은 3, recur(3)의 return값은 1 이므로 
// dp[9] = Math.min(3, 1) + 1 ==> 1 + 1 ==> 2

 

3) recur(5) 재귀함수 실행

==> n = 5로 재귀함수 실행 -> dp[5] = recur(4) +1

==> n = 4로 재귀함수 실행

• recur(3)
  • recur(2)
    • recur(1)
  • recur(1)
• recur(2)
  • recur(1)

recur(1)이 될 때 까지 재귀를 한 결과,

recur(5)는 3번만에 recur(1)에 도달하는 것을 확인할 수 있다.

// recur(5)
dp[5] = recur(4) + 1;

// recur(4)
dp[4] = Math.min(recur(3), recur(2)) + 1;
// recur(3) = 2, recur(2) = 1 이므로 
// dp[4] = Math.min(2, 1) + 1 ==> 2
// 그러므로 dp[5] = 3

 

4) Math.min(recur(9), recur(5)) : recur(9)와 recur(5)의 결과 중 더 작은 값을 판단

위 (2)와 (3)의 결과로

recur(9) == 2 이고, recur(5) == 3 임을 알 수 있다.

그러므로 Math.min(2, 3) ==> 2

 

5) dp[10] = Math.min(recur(9), recur(5)) + 1;

dp[10] = 2 + 1 ==>  3

---

재귀로 풀이했을 시, Math.min() 변수 순서에 따라 시간초과가 될 수 있음에 유의

Math.min(recur(n-1), recur(n/3))  -> Math.min(recur(n/3), recur(n-1))

recur(n-1)이 먼저 실행되면 n-1번 recur함수가 실행되어 재귀 깊이가 깊어지고 속도가 오래 걸리지만,

recur(n/3)과 recur(n/2)가 먼저 실행되면 recur(1)에 도달하는 속도가 빨라지기 때문에

Math.min()의 파라미터로 입력된 함수 순서가 시간에 영향을 미친다.

참고: https://www.acmicpc.net/board/view/95505