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

문제 설명

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

프로그래머스

 

문제를 어떤 식으로 접근해야 할지 감이 잡히지 않는다면,

테스트케이스를 보고 정답값이 어떻게 도출되는지 따라가 봅시다.

 

 

(이것은 머리 아프다고 포기한 스스로에게 하는 얘기)

 

 

인터넷에 검색해 보니 이런 식으로 1,1,2,5,14,... 도출된 값을 카탈란 수라고 하더라고요..? 응용 문제가 꽤나 있으니 이번 기회에 머릿속에 저장합시다. 위키에서 참고한 공식을 토대로, 아래에 계산 과정을 나열해 보았습니다.

 

 

코드 구현

def solution(n):
        
    dp = [0]*(n+1)
    dp[0] = 1
    dp[1] = 1

    for i in range(2,n+1):
        for j in range(i):
            print(i,"->", i-j-1, j, dp)
            dp[i] += dp[i-j-1] * dp[j]

    return dp[n]

print(solution(4))

# 입력 : 4
# 2 -> 1 0 [1, 1, 0, 0, 0]
# 2 -> 0 1 [1, 1, 1, 0, 0]
# 3 -> 2 0 [1, 1, 2, 0, 0]
# 3 -> 1 1 [1, 1, 2, 2, 0]
# 3 -> 0 2 [1, 1, 2, 3, 0]
# 4 -> 3 0 [1, 1, 2, 5, 0]
# 4 -> 2 1 [1, 1, 2, 5, 5]
# 4 -> 1 2 [1, 1, 2, 5, 7]
# 4 -> 0 3 [1, 1, 2, 5, 9]
# 출력 : 14

 

점화식을 도출하면 이후 구현은 아주 간단합니다. 

이해는 알아서.

(이것 또한 스스로에게 하는 얘기)