[BOJ] 백준 10422 괄호 Python

#10422 괄호
import sys
import math
input = sys.stdin.readline
p = 1000000007
def catalan(n):
    return (math.factorial(2*n) // (math.factorial(n+1) * math.factorial(n))) % p

N = int(input())
result = []
for i in range (0,N):
    a = int(input())
    if a % 2 != 0:
        result.append(0)
    else:
        result.append(catalan(a//2))

for i in range (0,N):
    print(result[i])

카탈랑 수에 대한 내용이다.

과거 KMO (이젠 추억이 되어버린 올림피아드 ㅋㅋ;)를 준비하면서 공부한 기억이 있어서 바로 적용할 수 있었다.

이와 비슷한 레파토리로,

• +(+1)와 -(-1)로 이루어진 sequence에서, +와-를 각각 n번씩 사용하여 2k번째마다 (k=1,2,3 ....,n) 항상 0이상이 되게끔 만드는 수열의 갯수를 구하시오 등등 ...
• 계단의 오르막과 내리막을 같은 갯수씩 부여하고, 지하에 들어가지 않게끔 코스를 짜는 방법 etc ...

이런 문제들이 많이 있었다.
이제는 다 까먹어버려서 포함배제, 비둘기집의 원리, 카탈랑수, 중복조합, 중복순열 이런것들밖에 기억이 안 나지만 ...

그래도 프로그래밍을 하면서 이런 옛날 추억이 다시 한번씩 떠오르는게 좋은 것 같다.

 

아차. 코드 설명에 대한것을 첨언하자면,

given int a가 홀수인 경우에는, 절대 닫힐 수 없으므로 이에 유의하고 항상 0으로 만들어주자.
짝수인 경우에는, 위의 설명과 같이 n = 2k 꼴로 생각한 뒤 k번째 catalan 수를 대입해주면 된다.