프로그래머스 [Lv. 4] 올바른 괄호의 갯수 {언어 : Python} [다시 풀어 보기]

문제 링크

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

프로그래머스

정답 코드

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

풀이 방법

1. 점화식은 다음과 같다.
2. f(n) = f(1) * f(n-1) + f(2) * f(n-2) + ... + f(n-1) * f(1)
3. 점화식에 따라 동적 계획법을 사용하면 끝!

느낀점

• dp인 것은 알지만 점화식을 올바르게 세우는 것이 어려웠던 문제