[프로그래머스] Level 4. 올바른 괄호의 개수

https://school.programmers.co.kr/learn/courses/30/lessons/12929?language=cpp

프로그래머스

 

만약 N개의 괄호쌍이 있다고 했을때, 가능한 조합은 다음과 같이 진행된다

 

( <i개의 조합쌍> ) <N-1-i 개의 조합쌍> 

 

으로 볼 수 있다. 여기서 i는 0~n-1까지 가 될 수 있다.

예를들어 n =3 일때,

( <0개조합쌍> ) <2개조합쌍> = ()()() , ()(())

( <1개조합쌍> ) <1개조합쌍> = (())()

( <2개조합쌍> ) <0개조합쌍> = (()()), ((())) 

 

으로 총 5개가 나온다. 이를 수식으로 바꾸면

f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-2)*f(1) + f(n-1)*f(0) 이다.

 

앞에 값들이 자주 사용되므로, vetor<int> 를 선언하여 이전의 연산값을 보유하도록 한다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    
    vector<int> sums(n+1,0);
    sums[0] = sums[1] = 1;
    for(int i=2; i<=n; i++){
        for(int j=0; j<i; j++){
            sums[i]+=sums[j]*sums[i-j-1];    
        }
    }
    return sums[n];
}

 

쉽군!