[PROGRAMMERS] 올바른 괄호 - 카탈란 수

출처 : http://suhak.tistory.com/77

#include<iostream> #include<vector> using namespace std; /* 만약 ( 괄호가 나오면 반드시 ) 괄호가 나와야 함. ( 이 두 번 나오면 ) 도 반드시 두 번 나와야 함. 쌍을 이루는 것들을 나열하는 모든 경우의 수를 카탈란 수라고 한다. (1) 첫 번째는 2차원 배열에서 한 지점 A에서 B까지 가는 최단경로의 수다. 왜냐하면, A에서 B지점까지 최단경로로 도착하기 위해선 단 두 가지 방향의 쌍으로 이루어진다. 가장 간단히 다음과 같은 배열이 있다. 0 0 B 0 0 0 A 0 0 여기서 A에서 B로 최단경로로 도착하려면, 오른쪽아니면 위쪽 밖에 길이 없다. 그리고 반드시 이 방향은 대칭된다. 그렇기에 카탈란 수에 속한다. (2) n개의 노드로 이루어진 이진 탐색트리(Binary Search Tree) 괄호쌍이나 2차원 배열 최단경로 수랑은 조금 다르다. 왜냐하면 자식노드의 왼쪽 오른쪽 쌍의 개수가 대칭을 이루지는 않는다. 하지만, 다음의 예를보면 왼쪽 자식 노드 0개, 오른쪽 자식 노드 n-1개. 왼쪽 자식 노드 1개, 오른쪽 자식 노드 n-2개. 왼쪽 자식 노드 2개, 오른쪽 자식 노드 n-3개. .................. 왼쪽 자식 노드 n-1개, 오른쪽 자식 노드 0개. 트리의 구조가 대칭쌍을 이루기에 카탈란 수에 속한다. */ vector<vector<int> > cache; int parenthesisCase(int n) { int answer = 0; if (n != 0) { for (int i = 0; i <= n; i++) cache[0][i] = 1; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { cache[i][j] = (cache[i - 1][j] + cache[i][j - 1]) % 10007; } } answer = cache[n][n]; } return answer; } int main() { int test; cin >> test; cache = vector<vector<int> >(test + 1, vector<int>(test + 1)); //C++에서는 정답을 10007로 나눈 나머지를 출력해 주세요. cout << parenthesisCase(test); return 0; }