[programmers/py] 올바른 괄호 갯수

올바른 괄호 갯수

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

문제 설명

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

풀이

카탈란 수 문제

- Chat gpt 설명 -
카탈란 수의 점화식을 유도하는 과정은 다음과 같습니다.

우선, n개의 쌍을 이루는 올바른 괄호의 모든 경우의 수를 구해보겠습니다.

왼쪽 괄호와 오른쪽 괄호가 하나의 쌍을 이루는 경우를 생각해 봅시다. 이 경우는 n-1쌍의 괄호 내에 있는 올바른 괄호를 만드는 방법에 하나의 왼쪽 괄호와 하나의 오른쪽 괄호를 추가하는 것과 같습니다.
이제 이 괄호 쌍이 다른 쌍의 내부에 위치하는 경우를 생각해 봅시다. 즉, n-2쌍의 괄호 내에 있는 올바른 괄호를 만드는 방법에 하나의 왼쪽 괄호와 하나의 오른쪽 괄호를 삽입한 후, 남은 괄호로 올바른 괄호를 만들어야 합니다.
이러한 패턴을 반복하여 모든 경우의 수를 합산하면, n쌍의 올바른 괄호를 만드는 방법의 수를 얻을 수 있습니다.
이를 수식으로 표현하면 다음과 같습니다.

C(n) = C(0) * C(n-1) + C(1) * C(n-2) + ... + C(n-1) * C(0)

여기서 C(k)는 k쌍의 올바른 괄호를 만드는 방법의 수를 나타냅니다.

따라서, 카탈란 수의 점화식은 이러한 패턴에서 유도되었습니다. 이를 일반화하면 다음과 같이 표현됩니다.

C(n+1) = Σ (C(i) * C(n-i)) for i = 0 to n

여기서 Σ는 모든 i에 대해 합을 구하는 기호입니다.

def solution(n):
    dp = [0]*(n+1)
    dp[0] = 1
    for i in range(n+1):
        for j in range(i):
            dp[i] += dp[j] * dp[i-j-1]
    return dp[-1]