[백준] CLASS3 1463 1로 만들기 - JAVA [자바]

안녕하세요. 이번에는 백준 1463 1로 만들기 문제를 풀어보려고 합니다.

 

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

1463번: 1로 만들기

---

Problem

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

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

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

사진 1. 문제

---

Solution

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.print(recur(N));
    }

    static int recur(int N) {
        if(dp[N] == null) {
            if(N % 6 == 0) {
                dp[N] = Math.min(recur(N - 1), Math.min(recur(N / 3), recur(N / 2))) + 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];
    }
}

---

Performance

사진 2. 실행 결과