[백준] 15990 1, 2, 3 더하기 5 - 동적계획법(Dynamic Programming, DP) JAVA

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

15990번: 1, 2, 3 더하기 5

코드설명

DP 문제입니다.

 

1, 2, 3 더하기 문제에 같은 수를 두번 이상 연속해서 사용하면 안되는 조건이 추가된 문제입니다.

DP[N][1] : N을 만들때 끝자리가 1인경우

DP[N][2] : N을 만들때 끝자리가 2인경우

DP[N][3] : N을 만들때 끝자리가 3인경우

dp[1][1] = 1; // 1을 만들떄 끝자리가 1인 경우는 1개입니다. (1)
dp[1][2] = 0; // 1을 만들떄 끝자리가 2인경우는 없습니다.
dp[1][3] = 0; // 1을 만들떄 끝자리가 3인 경우는 없습니다.
 
dp[2][1] = 0; // 2를 만들때 끝자리가 1인 경우는 없습니다. ( 1 + 1 은 불가.(1이 연속) )
dp[2][2] = 1; // 2를 만들때 끝자리가 2인 경우입니다. (2, 1가지가 있습니다.)
dp[2][3] = 0; // 2를 만들떄 끝자리가 3인 경우는 없습니다.
 
dp[3][1] = 1; //3을 만들떄 끝자리가 1인경우는 (2+1)이 있습니다.
dp[3][2] = 1; //3을 만들떄 끝자리가 1인경우는 (1+2)이 있습니다.
dp[3][3] = 1; //3을 만들떄 끝자리가 1인경우는 (3)이 있습니다.

 

위와 같이 기본값을 세팅해줍니다.

 

아래에서 보듯, dp[i][1] = i-1의 숫자를 만들때 끝자리가 2인경우의수 + i-1의 숫자를 만들떄 끝자리가 3인경우의 수 를 해야 dp[i][1] 을 만들때 숫자가 연속되지 않습니다.

for(int i=4; i<=100000;i++) {
    dp[i][1] = ( dp[i-1][2] + dp[i-1][3] ) % mod;
    dp[i][2] = ( dp[i-2][1] + dp[i-2][3] ) % mod;
    dp[i][3] = ( dp[i-3][1] + dp[i-3][2] ) % mod;
}

 

코드

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int T, N;
	public static long[][] dp;
	public static long answer;
	public static long mod = 1000000009;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	dp = new long[100001][4];
    	dp[1][1] = 1; // 1
    	dp[1][2] = 0;
    	dp[1][3] = 0;
    	
    	dp[2][1] = 0; // 1 + 1 은 불가.(1이 연속)
    	dp[2][2] = 1; // 2
    	dp[2][3] = 0;
    	
    	dp[3][1] = 1; //2+1
    	dp[3][2] = 1; //1+2
    	dp[3][3] = 1; //3
    	
    	
    	for(int i=4; i<=100000;i++) {
    		dp[i][1] = ( dp[i-1][2] + dp[i-1][3] ) % mod;
    		dp[i][2] = ( dp[i-2][1] + dp[i-2][3] ) % mod;
    		dp[i][3] = ( dp[i-3][1] + dp[i-3][2] ) % mod;
    	}
    	
    	T = Integer.parseInt(st.nextToken());    	
    	for(int t=0;t<T;t++) {
    		st = new StringTokenizer(br.readLine());
    		N = Integer.parseInt(st.nextToken());
    		answer = ( dp[N][1] + dp[N][2] + dp[N][3] ) % mod;
    		System.out.println(answer);
    	}
    	
    	
    }
}

 

재귀를 활용한 코드입니다.

문제를 풀면서, cache[n] 까지는 알겠으나, cache[n][before]로 할경우 최적 부분구조(Optimal Substructure)를 만족하는가? 에 대한 확신이 들지 않았습니다. 이유는 before라는 과거값이 현재의 값에 영향을 주는가? 에 대한 의심 떄문입니다.

여전히, 완벽한 확신을 주지는 않지만, 어느정도 이해한 방식에 대해 서술합니다. 먼저, 아래의 재귀코드는 재귀형식이기에 결국 탑다운 형식이지만, 실제로 재귀형식의 특성에 의해 바텀업 방식으로 배열이 갱신됩니다.

만약, 2에서 0 을 호출했다고 합시다.

그러면, [0][2] = 0번쨰 n을 2번 숫자로 온경우.가 1로 갱신됩니다.

2의 입장에서는 [1][1]도 호출합니다만, [1][1]에서는 1이 이미 사용되었기에 [0][1] 로 갈 수는 없고, [-1][1] [-2][1] 이 호출되는데 이는 범위를 벗어나기에 [1][1] 은 결국 0이 됩니다.

이 값들이 반환되서 2에게 반환됩니다. 

보이시나요? 어떤 함수에서든 [2][0] (첫 Call)에서의 반환값은 항상 같은 것 입니다.

우리는 이를 캐싱해서 더이상 연산되지 않도록 만듭니다.

즉, [2][0] 의 입장에서는 어떤 방식으로든 만약 [2][0] 이 호출된다면 항상 값은 같습니다. 즉 최적 부분 구조(Optimial Substructure)가 성립합니다.

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, K, B, a, b;
	static int answer = 0;
	static int[] arr;
	static long[][] cache;
	static int MOD = 1000000009;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		cache = new long[1000001][4];
		for(int i=0; i<1000001; i++) {
			Arrays.fill(cache[i], -1);
		}
		while(T-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			long answer = DP(N, 0);
			System.out.println(answer);
		}
		
	}
	
	static long DP(int n, int before) {
		//기저사례 :
		if(n < 0) return 0;
		if(n == 0) return 1;
		
		if(cache[n][before] != -1) return cache[n][before];
		long ret = 0;
		if(n - 1 >= 0 && before != 1) {
			ret += DP(n-1, 1) % MOD;
		}
		if(n - 2 >= 0 && before != 2) {
			ret += DP(n-2, 2) % MOD;
		}
		if(n - 3 >= 0 && before != 3) {
			ret += DP(n-3, 3) % MOD;
		}
		return cache[n][before] = ret % MOD;
	}
 
}