[lv4] [해설안봄] 올바른 괄호 갯수

 

 

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

 

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요.

 

dp로 풀 수 있는 문제이다. 아이디어만 떠오르면 구현은 그렇게 어렵진 않은 것 같다.

 

우선 dp[괄호길이]   로 둔다.  dp[i] = 전체 문자열 길이가 i이고  처음과 끝이  ( ) 로 둘러싸인 괄호의 경우의 수

 

예를들면 dp[10] 에서의 예시로는   (   ()()()()     ) , (   (()()())    ) , (     ()(()())  ) ... 등이 있을 것이다.

dp 를 구하기 위해서는  재귀적인 방법을 사용하였다. 

예를들여 dp[10] 을 구하기 위해선  둘러싸고 있는 괄호 ( ) 을 제외한 길이가 8 인 괄호의 경우의 수를 구해야 한다.

 

dp[2] * dp[2] * dp[4]  =    (      길이가 2개인 괄호 경우의수 * 길이가 2개인 경우의 수 * 길이가 4개인 경우의수   ) 

이런식으로 말이다.

 

길이가 8인 괄호의 경우의 수의 예시로는  dp[2] * dp[2] * dp[2]*dp[2] , dp[2] * dp[2] * dp[4], dp[4] * dp[4] , dp[8]  ... 등등이 있을 것이다.

이러한 dp를 구하기 위해 재귀적인 방법을 사용한다.

 

현재위치가 0이면 앞으로 dp[2] or dp[4] or dp[6] or dp[8] 을 곱할 수 있다. 만약 dp[4] 를 곱한다면 현재위치를 4로 둔 함수를 재귀호출한다. 그럼 앞으로 dp[2], dp[4] 을 곱할  수 있다. 이렇게 하다보면 현재위치가 8에 도달 할 것이고, 그때 재귀를 종료하면 된다. 

 

  public void  calculationDp(int p , int total, int total_goal){
        int goal = total_goal - 2;
        if(p == goal){
            dp[total_goal]  += total;
            return;
        }
        for(int i = 2 ; p + i <=  goal ; i += 2){
           
            calculationDp(p + i, total * dp[i] , total_goal ); //  업데이트된 위치를 패러미터로 재귀함수 호출
            
        }
        
    }
}

 

이런식으로 dp [10] 을 구할 수 있다.

 

dp[2] = 1로 기본 setting 해놓고, 

재귀함수를 dp[4] 에 대해, dp[6] 에 대해,  dp[8] 에 대해... 반복문을 구하면 원하는 n에 대한 dp[n]을 구할 수 있다.