프로그래머스 - 올바른 괄호의 갯수 (level 4 연습문제) [Python]

 

 문제

 

programmers.co.kr/learn/courses/30/lessons/12929

코딩테스트 연습 - 올바른 괄호의 갯수

 

 

 

 

 

 

 문제 상황

 

- 괄호쌍의 개수를 입력받아 만들 수 있는 서로 다른 괄호쌍의 종류의 수를 출력한다.

 

 

 

 

 

 

 해결 전략

 

- 1, 2, 5, 14, 42로 증가하는 전형적인 카탈랑수 문제이다. 

 

 

 

 

 

 

 코드

 

def factorial(n:int) -> int:
    if n == 1:
        return 1
    return n*factorial(n-1)
def solution(n: int) -> int:
    return factorial(2*n)//((n+1)*(factorial(n)**2))

 

 

 

 

 

 

 

 

 해설

 

- 카탈랑 수는 (0,0)에서 (n,n)까지 갈 때 y = x를 넘어서지 않고 가는 방법의 수를 의미한다. 카탈랑 수는 (1/(n+1))*(2n!/n!*n!)이다. 구현부는 사실상 factorial 뿐이다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 문제를 해석하여 카탈랑 수임을 인지하기는 쉽지 않다. 1,2,5,14,42...의 수열을 보고 알아채도 된다.