[14517번] 팰린드롬 갯수 구하기 (Large)

문제 출처 :

https://www.acmicpc.net/problem/14517

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

3. 포함 배제의 원리

이 문제는 [14505번] 팰린드롬 갯수 구하기 (Small) :: http://www.crocus.co.kr/869 에서 상세하게 다뤘으니 참조하면 될 것같습니다.

차이점은 MOD를 해주는데 + MOD를 해주는 이유는 음수가 되는 과정을 방지하기 위해 작성하였고

마지막에 dp %= MOD를 해주면 됩니다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <cstring>
 
#define MAX 1010
#define MOD 10007
 
using namespace std;
 
long long dp[MAX][MAX];
char ch[MAX];
 
int main()
{
    int len, left, right;
    scanf("%s", ch);
 
    len = strlen(ch);
 
    for (int i = 0; i < len; i++)
    {
        // a 같은 경우
        dp[i][i] = 1;
 
        // aa 같은 경우
        if (ch[i] == ch[i + 1])
            dp[i][i + 1] = 3;
 
        // ab 같은 경우
        else
            dp[i][i + 1] = 2;
    }
 
    // L은 길이를 의미한다.
    for (int L = 2; L < len; L++)
    {
        for (left = 0; left < len; left++)
        {
            right = left + L;
 
            if (right > len)
                break;
 
            dp[left][right] = dp[left + 1][right] + dp[left][right - 1] - dp[left + 1][right - 1] + MOD;
 
            if (ch[left] == ch[right])
                dp[left][right] += dp[left + 1][right - 1] + 1;
            
            dp[left][right] %= MOD;
        }
    }
 
    printf("%lld\n", dp[0][len - 1]);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>