본문으로 바로가기

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

category PS/백준 2021. 4. 8. 23:19
문제

‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. 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


댓글을 달아 주세요