[2016 홍익대학교 프로그래밍 경진대회] 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)을 출력한다.

 

 

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
#include<set>
#include<map>
using namespace std;
long long dp[36];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		long long sum = 0;
		for (int j = 0; j <= i - 1; j++)
		{
			sum += dp[j] * dp[i - 1 - j];
		}
		dp[i] = sum;
	}
	cout << dp[n];
}