[Programmers] P12929 올바른 괄호의 갯수

[Programmers] P12929 올바른 괄호의 갯수

Question

Language: Python

Difficulty: Gold 4~5

만들 수 있는 괄호쌍의 개수를 구하는 문제이다.

n=1 -> ()

n=2 -> (()),()()

n=3 -> ()(()),()()(),(())(),((())),(()()),

해당 과정은 아래와 같이 분리해서 생각해볼 수 있다.

n=3 (0쌍)2쌍 -> ()(()),()()() (1쌍)1쌍 -> (())() (2쌍)0쌍 -> ((())),(()())

점화식은 아래와 같이 유도 할 수 있다.

dp[i]=dp[j-1]*d[i-j] #(1<j<n>)

주의점

처음에는 아래와 같이 고려했는데, 이렇게 하면 중복이 발생한다. 위의 방식처럼 한쪽 괄호 쌍을 왼쪽에 고정시켜놓고 고려를 하게 되면 중복을 피할 수 있다. (dp[i-1]) + dp[j]*dp[i-j] #(1<j<i)

위와 같은 알고리즘의 형태는 카탈랑 수의 형태이다. 이진트리의 개수, 격자 내에서의 경로 개수, 등 모두 카탈랑 수에 의거해서 나온 알고리즘이다.

catalan

Solution

def solution(n):
    answer = 0
    dp=[0]*(n+1)
    dp[0]=1
    dp[1]=1
    
    for i in range(2,n+1):
        for j in range(1,i+1):
            dp[i]+=((dp[j-1]*dp[i-j]))
          
    answer=dp[n]
    return answer