[C++] 백준 13699 - 점화식 [Silver 4]

출처

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

풀이 전략

문제에서 주어진 대로 점화식을 그대로 구현하기만 하면 된다.점화식이 조합에서 파스칼삼각형처럼 대칭을 이루고 있으므로 하나는 왼쪽에서, 다른 하나는 오른쪽에서 움직이면서 F[n]에 저장해놓으면 된다.

소스 코드

#include <iostream>
#include <vector>
using namespace std;

long long ignition(int n){
    long long F[n+1];
    F[0]=1;

    for(int i=1;i<=n;i++){
        F[i]=0;
        for(int j=0;j<i;j++){
            F[i]+=F[j]*F[i-j-1];
        } // 점화식
    }
    return F[n];
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    int N;
    cin>>N;
    long long result=ignition(N);
    cout<<result<<'\n';
    return 0;
}

결과