문제

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미한다.
괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환한다.

아이디어

핵심 아이디어

카탈란 수 - 수학과 사는 이야기

• 현재 괄호의 형태를 AB로 2분할 했다고 가정한다.
• 새로운 괄호 한 쌍을 추가하여 올바르게 괄호를 만들기 위해선 A와 B모두 올바르게 괄호가 형성되어있는 상태여야 한다.
• 하나의 괄호를 추가한다면 ()AB / (A)B / (AB) / A(B) / AB()형태가 될 수 있다.
• (A)B 형태로 모든 경우를 만들 수 있다.
  • 3쌍으로 구할 수 있는 올바른 괄호 갯수를 구했다 가정한 후, 4쌍으로 구할 수 있는 올바른 괄호 갯수를 구할 때
    1. len(A) == 0일 때, ( ) { 3 쌍의 괄호 } 형태가 된다.
    2. len(A) == 1일 때, ( { 1쌍의 괄호 } ) { 2 쌍의 괄호 } 형태가 된다.
    3. len(A) == 2일 때, ( { 2쌍의 괄호 } ) { 1 쌍의 괄호 } 형태가 된다.
    4. len(A) == 3일 때, ( { 3쌍의 괄호 } ) 형태가 된다.
  • ()AB는 1의 형태로 얻을 수 있다.
  • (A)B 는 2, 3의 형태로 얻을 수 있다.
  • A(B) 는 2, 3의 형태에서 얻은 상태이다.
  • AB() B의 길이가 0일 때, 3의 형태에서 얻을 수 있다.
  • (AB) 는 4의 형태로 얻을 수 있다.
• 따라서, AB를 분할하는 경우의 수를 구하면 된다.

구현 아이디어

1. dp[i] = sum(dp[j] * dp[i - j - 1]), j : 0 ~ i
2. dp[0], dp[1] = 1, 1로 초기값을 설정한다.
3. 2중 반복문을 통해 구현한다.

코드

def dp(n: int) -> int:
    memo = [0 for _ in range(n + 1)]
    memo[0], memo[1] = 1, 1
    for i in range(2, n + 1):
        for j in range(i):
            memo[i] += memo[j] * memo[i - j - 1]
    return memo[-1]

def solution(n):
    answer = dp(n)
    return answer