[백준 / 13699] 점화식 - C++

www.acmicpc.net/problem/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)을 출력하는 프로그램을 작성하시오.

 

입력 :0 이상 35 이하의 정수 n이 주어진다.

 

출력 : t(n)의 결과를 출력한다

 

점화식이 뭔지만 알면 쉽게 풀 수 있는 문제이다. 문제에 주어진 점화식을 코드로 구현하면 된다.

#include <iostream>
using namespace std;

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