[Python] 프로그래머스 Lv 4 - 올바른 괄호의 개수

와! 개꿀! 조합론 문제! 

출처 : programmers.co.kr/learn/courses/30/lessons/12929

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

 

알고리즘

여러 방법이 있을 것이다.

(1) 정석으로 정말 괄호 넣는 경우를 따져서 풀기... (...)

(2) 점화식 풀이

(3) 카탈란수인걸 알고 있는 자는 프리패스 하기.

 

(3)은 너무 양심이 없어, (2)로 진행할려고 한다.

(2)의 원리는 간단하다. n-1개의 괄호쌍이 완벽할 때, 1개를 더 추가한다고 보면 된다.

그경우, (A)B의 형태일 거고, A도 완벽하면 되고, B도 완벽하면 된다.

Cn = C0Cn-1 + C1Cn-2 + ... + Cn-1C0 으로 풀면 된다.

 

코드

def solution(n):
    answer = [1, 1]
    if n == 1:
        return 1
    else:
        for i in range(2, 15):
            count = 0
            for j in range(0, i):
                count += (answer[j]*answer[i-j-1])
            answer.append(count)
    return answer[n]

 

별해(노양심풀이), 카탈란수의 일반항이다.

import math
def solution(n):
    answer = math.factorial(2*n) / (math.factorial(n) ** 2) / (n+1)
    return answer