[JAVA][BOJ][S4] 13699. 점화식

13699번: 점화식

문제

다음의 점화식에 의해 정의된 수열 t(n)을 생각하자:

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

이 정의에 따르면,

• t(1)=t(0)*t(0)=1
• t(2)=t(0)*t(1)+t(1)*t(0)=2
• t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5
• ...

주어진 입력 0 ≤ n ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 n (0 ≤ n ≤ 35)이 주어진다.

출력

첫째 줄에 t(n)을 출력한다.

풀이

있는 그대로 적으면 된다....

코드

package 카탈란수;

import java.io.*;
import java.util.*;

public class s4_13699_점화식 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		long dp[] = new long[36];
		
		dp[0] = 1;
		dp[1] = 1;
		
		for(int i = 2; i<=35; i++) {
			for(int j = 0; j<i; j++) {
				dp[i] += (dp[j]*dp[i-j-1]);
			}
		}
		
		System.out.println(dp[n]);

	}

}

결과

 

#자바 #java #boj #백준 #알고리즘