[백준/Java] 1로 만들기 1463

 

 

 

문제 

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

1463번: 1로 만들기

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

풀이

 

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

이렇게 적지 않고

 

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

 

이렇게 recur(n - 1)이 앞에 온다면, 0부터 n - 1까지 모두 탐색되기 때문에 시간 초과가 된다.

그래서 우선 recur(n / 3)이나 recur(n / 2) 을 먼저 해서 부분을 메모이제이션을 한 다음, recur(n - 1)을 해주면 이미 탐색한 부분이 있으면 그 값이 반환되므로 탐색이 덜 걸리게 된다. 

 

 

메모이제이션(memoization)이란?

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

 

 

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

public class Main {
    static Integer[] dp;

    public 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];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        Main m = new Main();
        dp = new Integer[n + 1];
        dp[0] = dp[1] = 0;
        int answer = m.recur(n);
        System.out.println(answer);
    }
}

 

 

 

 

 

 

 

 

 

정답