올바른 괄호의 갯수

• 카탈랑 수를 해로 갖는 대표적인 문제

• 마지막 위치에는 닫는괄호())가 와야 한다. 이 괄호와 매칭되는 여는 괄호(()가 i번째에 있는 경우들로 나눠서 생각할 수 있다.
• 매칭되는 괄호가 i번째에 있으면..

  • ....(....)
        i    n

  • [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)에 계산이 가능하다. 카탈랑 수 (Catalan number) 참고

"""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)