프로그래머스 : 연습문제 > 올바른 괄호의 갯수(lv4) c++

프로그래머스 링크

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

프로그래머스

문제 설명

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

제한사항

• 괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수

---

입출력 예nresult

2	2
3	5

입출력 예 설명

입출력 예 #1
2개의 괄호쌍으로 [ "(())", "()()" ]의 2가지를 만들 수 있습니다.
입출력 예 #2
3개의 괄호쌍으로 [ "((()))", "(()())", "(())()", "()(())", "()()()" ]의 5가지를 만들 수 있습니다.

코드 풀이

문제를 보고 수학적 공식이 있을거 같다는 생각이 들어 관련 공식을 검색해 보니

카탈랑 수라는 공식을 확인할 수 있었다.

 

자세한 내용은 위키

https://ko.wikipedia.org/wiki/%EC%B9%B4%ED%83%88%EB%9E%91_%EC%88%98

카탈랑 수 - 위키백과, 우리 모두의 백과사전

 

코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int Array[15];

int solution(int n) {
    int answer = 0;
    
    Array[0] = 1;
    
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j <= i; ++j)
        {
            Array[i] += Array[j] * Array[i - j - 1];
        }
    }
    
    return Array[n];
}

정확성