백준] 13699 - 점화식(홍익대학교 프로그래밍 경진대회 2016)

시간 제한 : 5초

메모리 제한 : 512MB

입력

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

출력

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

소스코드

#include <iostream>
using namespace std;
int main()
{
	long long dp[36] = { 1, };
	int n;
	cin >> n;
	for (int i = 1; i <= 35; i++)
		for (int j = 0; j < i; j++)
			dp[i] += dp[i - j - 1] * dp[j];
	cout << dp[n];
}

Tip

점화식이 문제에 주어져 있는 셈이나 다름이 없다. 시간 제한 5초는 주어진 조건에 비하면 매우 널널한 편인 듯..

dp[i]=dp[i]+dp[i-j-1]*dp[j]