[프로그래머스] Lv4. 올바른 괄호의 갯수 - JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 4

출처 : 프로그래머스 - 올바른 괄호의 갯수

문제

제한사항

📌 내가 생각한 풀이

DP문제이다. 올바른 괄호이므로 반드시 괄호가 열리면서 시작해야한다. 여기서 핵심은 ()괄호가 미리 하나 존재한다고 생각하고, 그 안에 괄호의 갯수를 생각하는 것이다.
만약 n=3 일경우 경우의 수는 아래와 같다.
1. (0개의 가짓수) x 2개의 가짓수
2.(1개의 가짓수) x 1개의 가짓수
3. (2개의 가짓수) x 0개의 가짓수

function solution(n) {
  var answer = 0;
  let arr = new Array(n + 1).fill(0);
  arr[0] = 1;
  arr[1] = 1;
  arr[2] = 2;
  for (var i = 3; i <= n; i++) {
    for (var k = 0; k < i; k++) {
      arr[i] += arr[k] * arr[i - k - 1];
    }
  }
  return arr[n];
}

📌 느낀점

미리 한개의 괄호를 생각하는 것이 어려웠다. 단번에 DP문제임을 알았지만, 점화식을 세우는 것이 복잡하였다.