[백준] 17212 달나라 토끼를 위한 구매대금 지불 도우미 - 동적계획법(DP, Dynamic Programming)JAVA

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

코드설명

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

 

모든 동전을 최소한의 개수를 구하기 위해 완탐을 시도하면, 시간초과가 발생합니다.

이유는, N이 100,000 입니다. 이떄 가능한 모든 경우를 탐색할경우 O(4^n)입니다. 당연히 시간초과가 발생하겠습니다.

그러나, 메모이제이션을 활용할경우 모든 연산이 딱 한번만 진행되게 되기에 시간복잡도가 O(n)으로 변화됩니다.

코드

package Main;

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