[Javascript/PGS] Lv.4 : 올바른 괄호의 갯수 (DP)

 

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

프로그래머스

---

프로그래머스 레벨 4.

dp긴 한데, 감이 안 잡혀서 질문하기 게시판을 참고했다...ㅎ.ㅎ

곱셈 dp 문제는 처음인듯!!!

아래 풀이처럼, 괄호 한 쌍을 중심으로

()의 안에 들어가는 괄호 쌍, 그리고 밖에 나오는 괄호 쌍

경우의 수를 곱하면 된다.

 

예를 들어서 n=3일때는,

() / ()() -> 기준 괄호에 아무것도 들어가지 않음. 바깥에는 2개가 존재하므로 dp[0] * dp[2] = 1*2

(()) / () -> 기준 괄호에 1개, 바깥에 1개. dp[1] * dp[1] = 1*1

(()()) -> 기준 괄호에 2세트 들어가고, 바깥에는 0개. dp[2] * dp[0] = 2*1

따라서 dp[3] = 5이다.

 

출처 : https://school.programmers.co.kr/questions/50021

 

나의 풀이

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