[Programmers] 올바른 괄호의 갯수

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/12929

프로그래머스

 

올바른 괄호 문자열의 개수를 구하기 위해 카탈랑 수(Catalan Number)를 구해주면 되는 문제였습니다.

점화식은 다음과 같습니다.

 

 

	#include <string>
	#include <vector>
	using namespace std;
	int solution(int N) {
	vector<int> v(N + 1, 0);
	v[0] = 1;
	for (int num = 1; num <= N; num++)
	{
	for (int i = 0; i < num; i++)
	{
	v[num] += v[i] * v[num - (i + 1)];
	}
	}
	return v[N];
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE  

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~