Baekjoon 13699 점화식 JAVA

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)을 출력한다.

풀이

다이나믹 프로그래밍으로 문제의 점화식을 만족시키면된다.

값은 int의 범위를 벗어나기에 long을 이용하여 풀었다.

처음의 값을 1로 주고 점화식을 만들어서 모든 값을 저장하고 마지막에 index를 이용하여 값을 출력

코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		Long [] dp=new Long [40];
		dp[0]=(long) 1;
		for(int i=1;i<=35;i++) {
			dp[i]=(long) 0;
			for(int j=0;j<i;j++)
				dp[i]+=dp[j]*(dp[i-j-1]);
		}
		System.out.println(dp[n]);
	}
}