Study hard
(c++)백준 10422번: 괄호 본문
[풀이]
재귀 DP로 풀 수 있는 문제였다.
DP[x]: 길이 x인 올바른 괄호 문자열의 개수
#include <iostream>
#include <cstring>
using namespace std;
int T, L;
long long DP[5001];
long long solution(int len) {
//길이가 0이 될 때까지 재귀 돌렸으면
if (len == 0)
return 1;
long long& res = DP[len];
//이미 길이 len에 대한 개수를 구했으면
if (res >= 0)
return res;
res = 0;
for (int i = 0; i <= len; i+=2) {
res += solution(i)*solution(len - i - 2);
//메모리 초과 안 나게 계산할 때마다 %해주기
res %= 1000000007LL;
}
return res;
}
int main() {
cin >> T;
memset(DP, -1, sizeof(DP));
while (T--) {
cin >> L;
if (L % 2 == 1)
cout << 0 << '\n';
else
cout << solution(L) << '\n';
}
return 0;
}
'백준 > DP' 카테고리의 다른 글
(c++)백준 2294번: 동전 2 (0) | 2020.09.16 |
---|---|
(c++)백준 2293번: 동전 1 (0) | 2020.09.16 |
(c++)백준 12869번: 뮤탈리스크 (0) | 2020.09.15 |
(c++)백준 1459번: 기타리스트 (0) | 2020.09.15 |
(c++)백준 12865번: 평범한 배낭 (0) | 2020.09.15 |