[백준] 15989 1, 2, 3 더하기 4 - DP JAVA

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

코드설명

DP 문제입니다.

 

이 문제같은경우 예시와 함꼐 설명해보겠습니다.

아래처럼 dp가 완성됩니다.

이 문제에서 dp[][] 로 처리하는 이유는 1+1+2 와 1+2+1 과 2+1+1 이 같은 숫자로 처리되기 떄문입니다.

즉, dp[N][1] 은 N이라는 숫자를 만들면서 1로 끝나는 경우

dp[N][2] 은 N이라는 숫자를 만들면서 2로 끝나는경우

dp[N][3] 은 N이라는 숫자를 만들면서 3으로 끝나는경우

이렇게 3가지로 나뉩니다.

 

3가지로 나누는 이유는, 중복처리를 하지 않기위해 모든 경우의 수는 오름차순 형태의 경우로 생각하기 위함입니다.

즉, 1+1+2, 1+2+1, 2+1+1 이 있을때 반드시 1+1+2 형태로 만들어줍니다.

dp[1][1] = 1 -> 1
dp[1][2] = 0
dp[1][3] = 0;

dp[2][1] = 1 -> 1+1
dp[2][2] = 1 -> 2
dp[2][3] = 0;

dp[3][1] = 1 -> 1+1+1
dp[3][2] = 1 -> 1+2
dp[3][3] = 1 -> 3

dp[4][1] = 1 -> 1+1+1+1
dp[4][2] = 2 -> 1+1+2, 2+2
dp[4][3] = 1 -> 1+3

그러면 결과적으로 아래와 같은 점화식이 나옵니다.

//마지막 숫자보다 
for(int i=4; i<10001;i++) {
    dp[i][1] = dp[i-1][1]; // 1 을 더하여 i를 만들 수 있습니다.
    dp[i][2] = dp[i-2][1] + dp[i-2][2]; // 2 를 더하여 i를 만들 수  있습니다.
    dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3]; // 3을 더하여 i를 만들 수 있습니다.
}

dp[N][1] 에서 dp[N-1][1] ( N보다 1 작은 숫자에서 1로 끝나는 경우) 인 이유는 오름차순으로 늘어나야하고, 1로 끝나는데 N보다 1 작으므로 반드시 1밖에 들어가지 못합니다. 여기서 2가 들어갈경우 N보다 1 작은데 당연히 2는 안되겠지요.

dp[N][2] 에서 dp[N-2][1] ( N보다 2 작은 숫자에서 1로 끝나는경우) +  + dp[N-2][2] ( N보다 1 작은 숫자에서 2로 끝나는경우) 인 이유는 역시 마찬가지로 N보다 2 작으면서 1로 끝나는경우에는 2 가 들어갈 수 있습니다. N보다 2 작으면서 2로 끝나는 경우에는 마지막 수에 2가 들어갈 수 있습니다.

dp[N][3] 도 마찬가지입니다.

 

즉, 오름차순으로 처리하기 위해 위와 같이 처리합니다.

코드

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

public class Main {
	public static int K, N, M, T;
	public static long[][] dp = new long[10001][4];
	public static int answer = 0;
	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[][] 는 2번째 배열의 의미는 어떤 숫자로 조합이 만들어졌는지입니다.
    	dp[1][1] = 1; dp[1][2] = 0; dp[1][3] = 0; 
    	dp[2][1] = 1; dp[2][2] = 1; dp[2][3] = 0;
    	dp[3][1] = 1; dp[3][2] = 1; dp[3][3] = 1;
    	
    	for(int i=4; i<10001;i++) {
    		dp[i][1] = dp[i-1][1]; // 1 을 더하여 i를 만들 수 있습니다.
    		dp[i][2] = dp[i-2][1] + dp[i-2][2]; // 2 를 더하여 i를 만들 수  있습니다.
    		dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3]; // 3을 더하여 i를 만들 수 있습니다.
    	}
    	
    	for(int i=0;i<T;i++) {
    		st = new StringTokenizer(br.readLine());
    		N = Integer.parseInt(st.nextToken());
    		System.out.println(dp[N][1] + dp[N][2] + dp[N][3] );
    	}
    	
    }
}