출처 : https://www.acmicpc.net/problem/10422

문제

‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러 가지가 있다.

하지만 우리가 궁금한 것은 길이가 L인 올바른 괄호 문자열의 개수이다. 길이 L이 주어졌을 때 길이가 L인 서로 다른 올바른 괄호 문자열의 개수를 출력하는 프로그램을 만들어 보자.

입력

첫 번째 줄에 테스트케이스의 개수를 나타내는 T (1 ≤ T ≤ 100)가 주어진다. 두 번째 줄부터 각 테스트케이스마다 괄호 문자열의 길이를 나타내는 L이 주어진다. (1 ≤ L ≤ 5000)

출력

각 테스트 케이스에 대해 길이가 L인 올바른 괄호 문자열의 개수를 1,000,000,007로 나눈 나머지를 출력하시오.

---

아이디어

1. 양 끝 괄호를 제외하고, 내부 괄호의 시퀀스를 순열로 조합 ... wrong

---

코드

Mine 1 (Wrong / Factorial)

import sys
from math import factorial
input = lambda: sys.stdin.readline()

T = int(input())
for _ in range(T):
    L = int(input())
    if L%2 == 1:
        result = int(0)
    elif L == 2:
        result = int(1)
    else:
        result = factorial(L-2)//factorial((L//2)-1)**2
    ans = result%1000000007

    print(ans, sep='\n')

개선사항

result = $\frac{(L-2)!}{(\frac{L}{2} - 1)! * (\frac{L}{2} - 1)!}$
error example) "( ) ) ( ( )"

개선 -> 인덱스 x에서
[# of " ( "] =< [# of " ) "]

---

카탈란 수(Catlain Number)

쌍을 이루는 원소들의 수열을 구할 경우 사용할 수 있음.

관련 문제

1. 괄호 갯수

Image Source https://suhak.tistory.com/77

2. 산 만들기

Image Source https://suhak.tistory.com/77

3.대각선 피해가기

Image Source https://suhak.tistory.com/77

4. 정n다각형에서 대각선을 그어 삼각형으로 분할하는 방법 수

Image Source https://suhak.tistory.com/77

점화식 (for 괄호)

$n$쌍의 괄호를 나열하는 경우의 수를 $C_n$이라 하자.
$C_n$은 $C_{n-1}$에 "( )"를 알맞은 곳에 넣어주는 경우의 수

$k$개의 괄호쌍으로 이루어진 $A$
$n-k-1$개의 괄호쌍으로 이루어진 $B$
$C_{n-1} = AB$
$C_n = (A)B$

---

$C_1 =C_0 C_0$
$C_2 =C_0 C_1 +C_1 C_0$
$C_3 =C_0 C_2 +C_1 C_1+C_2 C_0$
$C_4 =C_0 C_3 +C_1 C_2+C_2 C_1 +C_3 C_0$
$\vdots$
$C_n = \sum_{k=0}^{n-1}{C_kC_{n-k-1}}$

---

Mine 2 (Catalian Number)

import sys
input = lambda: sys.stdin.readline()

d = [0]*2501 # 괄호쌍의 갯수이므로 5000//2 -> 2501
d[0] = 1

def cat(x): #catalian number
    if d[x] != 0:
        return d[x]
    else:
        for i in range(x):
            d[x] += d[i]*d[x-i-1]
            d[x] = d[x] % 1000000007 # 곱의 나머지 == 나머지의 곱
        return d[x]

for j in range(2501): #2501개 쌍의 괄호에 대해 카탈린 수 적용
    cat(j)

T = int(input())
for _ in range(T):
    L = int(input())
    if L == 1:
        result = int(0)
    elif L % 2 == 1:
        result = int(0)
    else:
        result = int(cat(L//2)) # L = 문자열의 총 길이. L//2 = 문자열 내 괄호쌍의 수
    print(result)

개선사항