(C++) - 백준(BOJ) 21739번 : 펭귄 네비게이터

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

21739번: 펭귄 네비게이터

카탈란 수열의 값을 구하는 문제였습니다.

 

접근법이 너무 어려워 아래 해설을 참조하게 되었습니다. 응용하기 너무 어렵네요 ㅠㅠ

https://www.acmicpc.net/board/view/68251 

글 읽기 - 제1회 숙명여자대학교 교내 알고리즘 경진대회 (SMUPC) 종료

 

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll d[10001] = { 1 }, MOD = 1e9+7;
int n;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for(int j = 0; j < i; j++){
            d[i] = (d[i] + d[j] * d[i-j-1] % MOD) % MOD;
        }
    }
    cout << d[n];
}