====== 올바른 괄호의 갯수 ======
  * 카탈랑 수를 해로 갖는 대표적인 문제

===== 풀이 =====
  * 마지막 위치에는 닫는괄호(**)**)가 와야 한다. 이 괄호와 매칭되는 여는 괄호(**(**)가 i번째에 있는 경우들로 나눠서 생각할 수 있다.
  * 매칭되는 괄호가 i번째에 있으면..
    * <code>
....(....)
    i    n
</code>
    * [0:i]까지가 올바른 괄호로 채워져야 하고, [i+1:n]까지가 올바른 괄호로 채워져야지 전체가 올바른 괄호가 된다.
  * 즉 dp[i] * dp[n-i-1]이 이 경우의 올바른 괄호의 갯수이다
  * 이것을 모든 i에 대해서 합치면 dp[n] = dp[0]*dp[n-1] + dp[1]*dp[n-2] + ... + dp[n-1]*dp[0] 를 얻는다.
  * 이 점화식은 카탈랑 수의 점화식이고, 카탈랑 수는 닫힌 형태로 표현해서 O(n)에 계산이 가능하다. [[:ps:카탈랑 수]] 참고

===== 코드 =====
<dkpr py>
"""Solution code for "Programmers 12929. 올바른 괄호의 갯수".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/12929
- Solution link: http://www.teferi.net/ps/problems/programmers/12929
"""

import math


def solution(n):
    return math.comb(2 * n, n) / (n + 1)
</dkpr>

{{tag>프로그래머스 ps:problems:programmers:Level_4}}