[백준] 10422번 - 괄호 (C++) 문제 및 풀이

문졔) 백준 - 동적 계획법 (Dynamic Programming) - 괄호

-> https://www.acmicpc.net/problem/10422

10422번: 괄호

 

괄호의 길이가 L인 올바른 문자열의 개수를 구하고자 할 때, L은 다음과 같이 구할 수 있다.

solve(n)를 길이가 n인 올바른 문자열의 개수라 하면, 위의 문자열에서는 solve(L) = ∑ {solve(i - 2) * solve(L - i)}임을 알 수 있다. 또한, solve(i - 2)를 구하기 위한 작은 부분 문제가 반복되므로 memoization을 이용하여 이 문제를 해결할 수 있다.

 

 

 

C++ 소스 코드)