올바른 괄호의 갯수 (12929번) - 프로그래머스 (Programmers)

https://school.programmers.co.kr/learn/courses/30/lessons/12929

프로그래머스

 

 

프로그래머스 - 올바른 괄호의 갯수 (12929번)

난이도 : Lv 4

Time Complexity : O( N^2 )

 

---

 

 

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

 

 

★ 괄호의 쌍이 n개일 때 만들 수 있는 경우의 수를 f(n) 이라고 하면,

f(n)의 값은 아래와 같은 규칙을 따른다.

f(0) = 1
f(1) = 1
f(2) = f(1)*f(0) + f(0)*f(1)
f(3) = f(2)*f(0) + f(1)*f(1) + f(0)*f(2)
f(4) = f(3)*f(0) + f(2)*f(1) + f(1)*f(2) + f(0)*f(3)
...

 

위와 같이 나타나는 이유는 아래와 같다.

f(2)
- ( f(0) ) f(1)
- ( f(1) ) f(0)

f(3)
- ( f(0) ) f(2)
- ( f(1) ) f(1)
- ( f(2) ) f(0)

f(4)
- ( f(0) ) f(3)
- ( f(1) ) f(2)
- ( f(2) ) f(1)
- ( f(3) ) f(0)

...