24231 - 해석

 

 

step 1

dp[i][j] : i번째 부터 j번째 까지만 있다고 했을 때 만들 수 있는 올바른 괄호 문자열의 개수

step 2

dp[i][j]를 채운다고 생각해 봅시다. i번째 문자는 반드시 여는 괄호여야 합니다. 이 문자는 i+1, i+3. i+5,... 번째 문자와 짝을 이룰 수 있습니다(물론 그 문자는 닫는 괄호여야 합니다). 만약 k번째 문자와 짝을 이루었다면 dp[i][j] += dp[i+1][k-1] * dp[k+1][j]를 해줍니다.

이런 식으로 dp를 채워나가면 됩니다. 탐색 순서는 j-i가 작은 순서대로 탐색하면 됩니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
long long int mapp[400][400];
char b[500];
int main() {
    long long int l, i,j,k;
    scanf("%s", b);
    l = strlen(b);
    for (i = 0;i < l-1;i++) {
        if (b[i] != b[i + 1]) mapp[i][i + 1] = 1;
    }
    for (i = 4;i <= l;i+=2) {
        for (j = 0;j < l;j++) {
            if (j + i - 1 >= l) break;
            if (b[j] != b[j + i - 1]) {
                mapp[j][j + i - 1] = mapp[j + 1][j + i - 2];
            }
            for (k = j + 1;k <= j + i - 3;k += 2) {
                if (b[j] == b[k]) continue;
                mapp[j][j + i - 1] += ((j+1==k ? 1 : mapp[j+1][k-1]) * mapp[k + 1][j + i - 1])% 1000000007;
                mapp[j][j + i - 1] %= 1000000007;
            }
        }
    }
    printf("%lld", mapp[0][l-1]% 1000000007);
    return 0;
}