[백준 13699번] 점화식 (C++)

문제링크 : https://www.acmicpc.net/problem/13699

13699번: 점화식

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll dp[36];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N;
    cin >> N;

    dp[0]=1;

    ll result = 0;
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=i; j++)
        {
            dp[i] += dp[j-1]*dp[i-j]; //점화식
        }
    }

    cout << dp[N];
    return 0;
}

문제에 점화식을 그대로 따라하면 되는 DP 문제이다.

수의 범위가 커서 long long으로 선언해야 한다.

 

문제의 점화식을 보면

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, 1, 2 ... 하나씩 커지고

하나는 2, 1, 0 ... 하나씩 작아지는 것을 볼 수 있다.

 

따라서 t(N) = t(i-1)* t(N-i) 대략 이런  점화식을 구할 수 있다.

이중 반복문을 두고, 저기서 N을 첫 번째 반복문의 i, i를 두번째 반복문의 j로 두고 해당 i일때의 dp를 구하도록 해준다.