[백준] 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++ 소스 코드)

 

	#define _CRT_SECURE_NO_WARNINGS
	#include <bits/stdc++.h>
	#define endl "\n"
	#define ll long long
	#define loop(i, n) for(int i = 0; i <n;++i)
	#define INF 987654321
	#define MAX 5001
	#define MOD 1000000007
	using namespace std;
	ll cache[MAX];
	ll solve(int L) {
	if (L % 2 == 1) return 0;
	if (L == 0 || L == 2) return 1;
	ll& ret = cache[L];
	if (ret != -1) return ret;
	ret = 0;
	for (int i = 2; i <= L; i++) {
	ret += (solve(i - 2) * solve(L - i));
	ret %= MOD;
	}
	return ret;
	}
	int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int T; cin >> T;
	memset(cache, -1, sizeof(cache));
	while (T--) {
	int n;
	cin >> n;
	cout << solve(n) << endl;
	}
	return 0;
	}

view raw 10422.cpp hosted with ❤ by GitHub