[백준/Python(파이썬)] 10422 괄호

문제

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

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

입력

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

출력

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

풀이

dp 문제. 점화식 세우다가 도저히 안되서 검색해봤다.

카탈란 수를 사용해서 푸는 문제였다.

 

카탈란 수 알고리즘이란 점화식이 다음과 같은 모습을 지닐 때를 말한다.
Catalan(n) = 2n! / (n! * (n+1)!)

한 가지 경우를 시행하면, 그와 쌍이되는 다른 경우를 반드시 시행해야 하는 모든 개수
예) 괄호쌍의 경우, (가 나오면 반드시 )가 나와야 함
(가 두 번 나오면 ) 또한 두 번 나와야 함

 

Python으로 표현하면 아래와 같음.

import math

def catalan(n):
reutrn math.factorial(2*n) // (math.factorial(n) * math.factorial(n+1))

종이에 그려가면서 풀었는데 결국 못 풀었다. 새로운 알고리즘 정리

소스코드

import math
def catalan(n):
    return math.factorial(2*n) // (math.factorial(n) * math.factorial(n+1))

t = int(input())
n = []
for i in range(t):
    n.append(int(input()))
for i in n:
    if i % 2 == 1:
        print(0)
    else:
        print(catalan(i//2)%1000000007)

Git : github.com/jisun1125/algorithm-problem-solving/blob/main/baekjoon/no_10422.py

문제 : www.acmicpc.net/problem/10422