괄호

Problem link: https://www.acmicpc.net/problem/10422

DP의 고전 of 고전 카탈란 수 문제이다.

별다른 풀이는 없지만, 기억 열화를 막고자 점화식을 떠올리는 방법을 아래와 같이 적어 놓는다.

편의상 N이 6이었다고 할 때, 아래 경우의 수를 헤아리면 중복/빠짐 없이 모든 경우를 헤아리게 된다.

• ( ) _ _ _ _
• ( _ _ ) _ _
• ( _ _ _ _ )

#include <iostream>
#include <cstdint>

using namespace std;

const int64_t kMod = 1000000007;
int64_t CACHE[5000 + 1];

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Solve all
  CACHE[0] = 1;
  CACHE[2] = 1;
  for (int64_t n = 4; n <= 5000; n += 2)
  {
    for (int64_t closing = 1; closing <= n; closing += 2)
    {
      CACHE[n] += CACHE[closing - 1] * CACHE[n - closing - 1];
      CACHE[n] %= kMod;
    }
  }

  int64_t tc;
  cin >> tc;

  while (tc--)
  {
    int64_t n;
    cin >> n;
    cout << CACHE[n] << '\n';
  }

  return 0;
}