[백준] 2688 줄어들지 않아 - 동적계획법(DP, Dynamic Programming) JAVA

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

2688번: 줄어들지 않아

코드설명

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

 

DP[65][10]의 의미는, [65]의 의미는 자리수를 의미하며, [10]은 끝나는 숫자를 의미하며 DP가 저장하고있는값은 해당 자릿수이면서 끝나는 숫자가 [10]인 것중에서 줄어들지 않는 수의 개수를 저장하고 있습니다.

즉, DP[3][4] 라고 한다면 3자리 수의 4로 끝나는 숫자 중에서 줄어들지 않는 수의 개수를 구하라는 의미입니다.

 

DP[1][0] ~ DP[1][9]는 모두 1 입니다. 하나의 자리수는 모두 그 자체로 줄어들지 않는 수 1개입니다.

DP[2][0] = DP[1][0] 입니다. 즉, "00"을 의미합니다.

DP[2][1] = DP[1][0] + DP[1][1] 입니다. 즉, "01", "11" 을 의미합니다.

DP[2][2] = DP[1][0] + DP[1][1] + DP[1][2]; //02, 12, 22 를 의미합니다.

 

위의 식을 계속해서 진행하면됩니다.

 

또한, 이떄 자료형은 long형을 사용해야 합니다. 이유는 64개의 자리수를 총 최악의 경우 10번씩 64번 선택해야하기에 10^64 개 숫자가 주어질 수도 있기에 그렇습니다. 물론 이 숫자가 직접적으로 사용되는것은 아니지만, 이러한 범위의 숫자가 Counting되기에 long형이 필요합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int T, N;
	public static long answer = 0;
	public static long[][] DP = new long[65][10];
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	T = Integer.parseInt(st.nextToken());
    	
    	DP[1][0] = 1; //0
    	DP[1][1] = 1; //1
    	DP[1][2] = 1; //2
    	DP[1][3] = 1; //3
    	DP[1][4] = 1; //4
    	DP[1][5] = 1; //5
    	DP[1][6] = 1; //6
    	DP[1][7] = 1; //7
    	DP[1][8] = 1; //8 
    	DP[1][9] = 1; //9
    	
//    	DP[2][0] = DP[1][0]; //00
//    	DP[2][1] = DP[1][0] + DP[1][1]; //01, 11
//    	DP[2][2] = DP[1][0] + DP[1][1] + DP[1][2]; //02, 12, 22 
    	
    	for(int i=2;i<65;i++) {
    		for(int j=0;j<10;j++) {
    			for(int k=0;k<=j;k++) {
    				DP[i][j] += DP[i-1][k];	
    			}
    			  
    		}
    	}
    	
    	for(int i=0;i<T;i++) {
    		answer = 0;
    		st = new StringTokenizer(br.readLine());
    		N = Integer.parseInt(st.nextToken());
    		for(int j=0;j<10;j++) {
    			answer += DP[N][j];
    		}
    		System.out.println(answer);
    	}
    	
	}

}

 

정답코드2입니다. 재귀와 메모이제이션을 활용합니다.

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 {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T, d, c;
	static int answer = 0;
	static long[][] cache = new long[65][10];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=0;i<65; i++) {
			Arrays.fill(cache[i], -1);
		}
		
		T = Integer.parseInt(st.nextToken());
		while(T-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			System.out.println(DFS(-1, -1));
		}
	}
	
	static long DFS(int depth, int num) {
		if(depth == 0) return 1;
		long ret = 0;
		if(depth == -1 && num == -1) {
			for(int next = 0; next < 10; next++) {
				ret +=  DFS(N - 1, next);
			}
			return ret;
		}
		
		if(cache[depth][num] != -1) { return cache[depth][num]; }
		
		for(int next = num; next < 10; next++) {
			ret += DFS(depth - 1, next);
		}
		return cache[depth][num] = ret;
	}
	
}

 

 

처음에 정답코드2를 제출하면서 틀렸었던 오답코드입니다.

왜 틀렸었을까요? 이유는 최적 부분 구조를 만족하지 않았기 때문입니다.

정답코드2의 경우에는 depth가 N-1부터 내려오면서 시작되기에 최적 부분구조를 성립합니다.

반면에, 오답코드의 경우에는 depth가 0부터 시작되도록하였기에 1->2->3 으로 caching되며, 만약 cache[3][0]일 경우 cache[2]의 값을 가져오게되는 것 입니다.

이런 코드 작성시에는 항상 TOP-DOWN 방식으로 함수의 메모이제이션의 최적 부분 구조를 성립하게 해야합니다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T, d, c;
	static int answer = 0;
	static int[][] cache = new int[65][10];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=0;i<65; i++) {
			Arrays.fill(cache[i], -1);
		}
		
		T = Integer.parseInt(st.nextToken());
		while(T-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			System.out.println(DFS(-1, -1));
		}
		
	}
	
	static int DFS(int depth, int num) {
		if(depth == 0) return 1;
		int ret = 0;
		if(depth == -1 && num == -1) {
			for(int next = 0; next < 10; next++) {
				ret +=  DFS(N - 1, next);
			}
			return ret;
		}
		
		if(cache[depth][num] != -1) { return cache[depth][num]; }
		
		for(int next = num; next < 10; next++) {
			ret += DFS(depth - 1, next);
		}
		return cache[depth][num] = ret;
	}
	
}