올바른 괄호의 갯수

https://school.programmers.co.kr/learn/courses/30/lessons/12929

프로그래머스

 

카탈랑 수 를 알면 쉽게 풀 수 있는 문제입니다.

 

저는 카탈랑 수를 몰랐기에 다른 블로거 분의 도움을 받아서 해결했습니다.

참고

function solution(n) {
  const c = new Array(n + 1).fill(0);
  c[0] = c[1] = 1;

  // c(n) = E(i=0..n){C(i)*C(n-i)}
  function get_c(i) {
     if(c[i] != 0) return c[i];
     for (let j = 0; j < i; j++) {
        c[i] += get_c(j) * get_c(i - 1 - j)
     }
     return c[i];
  }

  return get_c(n);
}