[백준] 25418 정수 a를 k로 만들기 - 동적계획법(Dynamic Programming, DP) JAVA

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

코드설명

동적계획법(Dynamic Programming, DP)  을 활용합니다.

 

문제에서 특이사항은, 재귀로 구현하다보니 Memory StackOverflow가 발생합니다.

예제 3번의 경우나 1 1000000 을 입력하면 재귀가 너무 깊어지는데, 실제로 제출을 하면 예제가 통과합니다.

제 시스템에서 보다 더 많은 메모리를 BOJ에서 제공하고 있습니다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	private static int C, N, M, W, H, K, A;
    private static int answer = 0;
    private static final int MAX = 1000001;
    private static int[] cache = new int[MAX];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        A = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        Arrays.fill(cache, -1);
        answer = func(A);
        System.out.println(answer);
    }
    
    private static int func(int n) {
    	if(n > K) {
    		return MAX;
    	}
    	if(n == K) {
    		return 0;
    	}
    	if(cache[n] != -1) return cache[n];
    	int ret = MAX;
    	ret = Math.min(func(n * 2) + 1, func(n + 1) + 1);
    	return cache[n] = ret;
    }
    
}