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

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

13699번: 점화식

dp 문제였습니다.

 

 

📕 풀이방법

📔 입력 및 초기화

 i항의 값을 저장할 일차원 t배열, int 형 변수 n을 선언 후 n을 입력받습니다.

 

📔 풀이과정

top down dp를 통해 답을 반환해줍니다. 재귀함수의 동작방식은 이렇습니다.

 

 1. 기저 케이스는 항이 음수가 될 경우 0을 반환, 1또는 0인 경우엔 1을 반환해줍니다.

 

 2. 메모이제이션을 통해 불필요한 함수 호출을 방비합니다

 

 3. 현재항 num에 대해 for문을 돌며 수행합니다.

 

 4. 수행한 결과 값을 반환해줍니다.

 

📔 정답출력

dp재귀함수의 결과값을 반환 후 이를 출력합니다.

---

📕 Code

top down

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll t[36], n;

ll dp(int num){
    if(num < 0) return 0;
    if(num == 1 || num == 0) return 1;

    ll &ret = t[num];
    if(ret != -1) return ret;

    ret = 0;
    for(int i = 0; i < n; i++) ret += dp(num - i - 1) * dp(i);
    
    return ret;
}

int main(){
    memset(t,-1,sizeof(t));
    cin >> n;
    cout << dp(n);
}