[프로그래머스,java] level4: 올바른 괄호의 갯수

 

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

프로그래머스

 

문제는 매우간단

 

실제로 나오는 코드도 매우 간단하게 나오긴한다.

 

근데  문제 ->  코드로 가는 그 사고력.. 그게 어려우니 레벨 4였던것같다.

 

 

 

괄호.. 2쌍이 생겨나는 경우를 한번 살펴보자.

 

 

괄호 2쌍은  ()()  ,  (())   2개의 경우다. 

 

(())은   이전 괄호 1쌍에있던 모든 경우를  마치 감싸듯이 나오는 형태고,

 

()() 는    괄호 1쌍을 2개 붙인경우다. EX)  f(1)*f(1) 

 

 

괄호 3쌍을 살펴보자.

 

(()()) ,  ((()))  형태가 있다.

이 형태역시  이전 괄호 2쌍에있던 모든 경우를 마치 감싸듯이 나온 형태다.

 

그리고  (())(),  ()(()),  ()()() 형태가 있다.

이 형태는,  f(2)의 덩어리와 f(1)을곱,  f(1)의 덩어리와  f(2)의 곱이다.  

 

즉 5개가 존재한다.

 

 

덩어리=  () 형태로 전체가 감싼 경우다.

 

즉, 2개의 DP를 생성한다.

 

dp1은 총합의 dp고,

dp2는  덩어리의 dp이다. () 형태로 전체 감싼것만 센 갯수

 

dp2[n] =   dp[n] 과 동일하다.  이전의 괄호쌍에 ()로 덮으면 같은 갯수가 나오기때문이다.

 

dp[n] = dp[n-1]*dp2[1] +  dp[n-2]*dp2[2] +  ...  dp[1]*dp[n-1] 이 성립한다.

 

즉,  A의 형태와 B덩어리의 형태의 조합의 모든 덧셈이다.

이걸 코드로나타내면 

 

class Solution {
    public int solution(int n) {
        int answer = 0;
       
        //총합 dp
        int[] dp = new int[n+1];
        //덩어리 dp
        int[] dp2 = new int[n+1];
 
 
 
        dp[1]=1;
        dp2[1]=1;
 
 
        for(int i=2;i<=n;i++){
            dp2[i]=dp[i-1];
 
            int sum =0;
            for(int j=1;j<=i;j++){
                sum+=dp[j]*dp2[i-j];
            }
            dp[i]=sum+dp2[i];
 
        }
        //f(3)= f(2),f(1)  
 
        return dp[n];
    }
}

 

 

다른 사람의 풀이: 

 

class Solution {
    public int solution(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
 
        for (int i = 2; i <= n; i++) {
            for(int j = 0; j < i; j++) {
                dp[i] += dp[i - j - 1] * dp[j];
            }
        }
 
        return dp[n];
    }
}