[백준] 13699 점화식 - Java

 

 

문제 출저

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

 

 

 

 

문제 풀이

t(0)=1
t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0)
점화식이 다음과 같은 수열이 주어집니다. 이 수열에 n의 값을 구해야 합니다. 

 

1차원 long 배열 dp를 생성하여 점화식을 저장합니다. 

 

 

 

소스 코드

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


/*
점화식
https://www.acmicpc.net/problem/13699
 */

public class Main {

    static long dp[];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dp = new long[36];
        dp[0] = 1;
        for (int i = 1; i < 36; i++) {
            for (int j = 0; j < i; j++) {
                long temp = (dp[j] * dp[i-j-1]);
                dp[i] += temp;
            }
        }

        System.out.println(dp[n]);

    }

}