[백준] 13699 점화식 - DP JAVA

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

13699번: 점화식

코드설명

간단한 DP문제입니다.

 

문제로직입니다.

1. long[] dp 는 각 점화식에서 수열 값을 의미합니다.

2. t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0)  이것을 한개씪 표현해보면 아래와 같이 됩니다.

     dp[0] = 1 = dp[0];
     dp[1] = 1 = dp[0] * dp[1];
     dp[2] = 2 = dp[0] * dp[1] + dp[1] * dp[0];
     dp[3] = 5 = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0];

만약 이걸, dp[35] 를 구했다고 해봅니다. 이걸 만약 직접 한개씩 재귀로 들어가면서 구한다면 시간초과가 날 것 입니다.

이와 같이 각 값을 미리 구하면서 메모리제이션을 활용한다면 시간초과가 나지 않습니다.

 

코드

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

public class Main {
	public static int N;
	public static String str = "";
	public static long[] dp = new long[36];
	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());
    	dp[0] = 1;
    	dp[1] = 1;
    	dp[2] = 2;
    	dp[3] = 5;
    	
    	for(int i=4;i<=35;i++) {
    		dp[i] = 0;
			for(int j=0;j<i;j++) {
				dp[i] += dp[j] * dp[i-j-1]; 
			}
			
    	}
    	
    	System.out.println(dp[N]);
    	
    }
	
	
}