백준 13699번: 점화식 (C++)

https://www.acmicpc.net/problem/13699

13699번: 점화식

---

Solved By: DP

 

Top-Down DP 방법을 사용했습니다. 재귀 호출로 선언하여 t(n) 값이 존재한다면 그대로 리턴하고, 존재하지 않는다면 t(n)을 구하여 리턴하는 방식으로 Memoization 기법이 상당히 드러나는 문제였습니다.

 

#include <iostream>
#define MAX 36
#define ll long long
using namespace std;

int n;
ll t[MAX];

ll sol(int p){
    if(t[p]) return t[p];
    else{
        ll temp = 0;
        for(int i = 0; i < p; i++){
            temp += (sol(i) * sol(p - 1 - i));
        }
        return t[p] = temp;
    }
}

int main(){
    cin >> n;
    
    t[0] = 1;
    cout << sol(n);
    return 0;
}