220508 - 올바른 괄호의 갯수

◾ 올바른 괄호의 갯수 : 프로그래머스 LEVEL 4

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

문제

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

---

입력

• 괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수

출력

• 가능한 모든 괄호 문자열의 개수

입출력 예

n	result
2	2
3	5

---

◾ 풀이

1. 해설

• https://bb-dochi.tistory.com/51
• https://suhak.tistory.com/77
• 카탈란 수 를 활용하여 해결할 수 있는 문제이다.
  • 카탈란 수(catalan number) : 이진 트리의 수 따위를 셀 때 등장하는 수열
  • 점화식
    • $C_{0}=1$
    • $C_{n+1}=\sum _{i+j=n}C_{i}C_{j}=C_{0}C_{n}+C_{1}C_{n-1}+\dotsb +C_{n}C_{0}\qquad (n\geq 0)$
  • 일반식 : $C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}={\frac {(2n)!}{n!(n+1)!}}$
  • 각각 n개의 왼쪽 괄호와 오른쪽 괄호를 나열하는 데 괄호가 서로 맞아떨어지는 문자열의 개수, 정n다각형에 대각선을 그어 삼각형으로 분할하는 방법의 수 등
• 계산 과정 : 왼쪽에 괄호 한쌍이 있다고 생각하고 계산
  • $C_{0} = 1$
  • 1쌍인 경우
    • () : 안, 밖에 괄호가 0쌍인 경우 $C_{0}C_{0}$
  • 2쌍인 경우
    • (()) : 안에 괄호 1쌍인 경우 $C_{1}C_{0}$
    • ()() : 밖에 괄호 1쌍인 경우 $C_{1}C_{0}$
  • 3쌍인 경우
    • ((())), (()()) : 안에 괄호 2쌍인 경우 $C_{2}C_{0}$
    • (())() : 안에 괄호 1쌍, 밖에 괄호 1쌍인 경우 $C_{1}C_{1}$
    • ()(()), ()()() : 안에 괄호 0쌍, 밖에 괄호 2쌍인 경우 $C_{0}C_{2}$

---

2. 프로그램

1. 카탈란 수 점화식 또는 일반식을 통해 $C_{n}$ 계산

# 코드
def solution(n):
    answer = 1

    dp = [0 for i in range(n+1)]
    dp[0], dp[1] = 1, 1

    for i in range(2, n+1):
        for j in range(i):
            dp[i] += dp[j] * dp[i-1-j]

    answer = dp[n]

    return answer

# 코드
def solution(n):
    answer = 1

    factorial = [1 for i in range(2*n+1)]

    for i in range(2, 2*n+1):
        factorial[i] = int(factorial[i-1] * i)

    answer = int(factorial[2*n] / (factorial[n] * factorial[n+1]))

    return answer