[JAVA]백준 13699번: 점화식

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

13699번: 점화식

1. 문제 설명

 

점화식이 아래와 같을 때 t(n)을 출력하는 프로그램을 작성하시오.

 

t(0)=1

t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0)

 

2. 풀이

 

1부터 시작해서 입력된 n까지 차례대로 점화식을 만들어 가면 된다.

 

int의 범위를 벗어날 수 있기 때문에 long으로 선언해야 되는 것 주의

 

3. 코드

// JAVA 11, 시간 : 128ms , 메모리 : 14288KB


import java.io.*;
public class Main {


    // int 범위 벗어나기에 long 형으로 선언
    public static long[] dp=new long[36];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        dp[0]=1;

        // 1부터 n까지 순서대로 점화식을 곱해가면 된다.
        for (int x = 1; x <= n; x++) {
            int index=x/2;

            for(int y=0;y<index;y++){
                dp[x]+=2*(dp[y]*dp[x-1-y]);
            }

            if(x%2==1){
                dp[x]+=dp[x/2]*dp[x/2];
            }
        }

        bw.write(String.valueOf(dp[n]));
        bw.flush();
    }
}