[백준 / java] 1463 : 1로 만들기

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

package boj1463;
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){
            if(n % 6 == 0){
                dp[n] = Math.min(recur(n/3),Math.min(recur(n/2),recur(n-1)))+1;
            }else if(n % 3 == 0){
                dp[n] = Math.min(recur(n/3),recur(n-1))+1;
            }else if(n % 2 == 0){
                dp[n] = Math.min(recur(n/2),recur(n-1))+1;
            }else{
                dp[n] = recur(n-1)+1;
            }
        }
        return dp[n];
    }
}

Integer등 wrapper class 배열의 초기값 : null
int 초기값 : 0

N=10일때

→ 2로 나누어떨어짐 : dp[10] = min(recur(5), recur(9)) + 1

• 5의 경우 → dp[5] = recur(4) + 1; → 4의 경우 : dp[4] = min(recur(2), recur(3)) + 1

  • 2의 경우 : dp[2] = 1

  • 3의 경우 : dp[3] = 1

    → dp[4] = 2

    → dp[5] = 3

• 9의 경우 → dp[9] = min(recur(3), recur(8)) + 1

  • 3의 경우 : dp[3] = 1

  • 8의 경우 : dp[8] = min(recur(4), recur(7)) + 1
    - 4의 경우 : dp[4] = 2
    - 7의 경우 : dp[7] = recur(6) + 1 → dp[4]보다 클수밖에 없으므로 생략

    → dp[8] = 3

    → dp[9] = 2

즉, (3 vs 2) + 1이므로 10 → 9 → 3 → 1로 간 3번이 최소횟수가 됨

참고 : https://st-lab.tistory.com/133