[14505번] 팰린드롬 갯수 구하기 (Small)

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

3. 포함 배제의 원리

우선적으로 이 문제를 풀기 위해서는 문제 이해부터 잘 해야 한다.

여기서 말하는 부분집합이라는 것은

abc가 있다면 a, b, c, ab, ac, bc, abc가 모든 부분 집합이다. 총 (2^n) - 1가지가 모든 집합이 가짓수가 된다.(공집합을 제외했기 때문)

결국 문제의 n제한이 30이면 2^30은 대략 10억이기에 TLE를 맞이 할 수 있다.

이 문제를 이제 DP로 접근할 것인데 포함 배제의 원리를 이용할 것이다.

DP의 정의는 다음과 같다.

DP[a][b] => a에서 b까지 인덱스의 단어중 팰린드롬이 되는 가짓수.

 

우선 가장 처음 나오는 for문에서 전처리를 해준다.

글자 하나로 이루어진 경우는 dp값이 1이다.

그리고 이제 i번째, i + 1번째의 구성이 aa같이 같은 글자면 dp 값은 a, a, aa로 3이 되고

그게 아니라면 a, b로 2가 될 것이다.

다음 아래 for문에서 이제 DP 점화식이 나온다.

dp[left][right] = dp[left + 1][right] + dp[left][right - 1] - dp[left + 1][right - 1];

이 의미는 그림으로 다음과 같다.

L-1에 대한 dp[left][right]를 구하기 위해서는 left+1과 right의 팰린드롬 개수(dp[left+1][right])를 더해주고

left와 right-1의 팰린드롬 개수(dp[left][right-1])를 더해주고

마지막으로 중복 처리된 dp[left+1][right-1]을 한번 빼준다.(포함 배제의 원리 이용)

이렇게 한다면 현재 dp[left][right]에는 L-1짜리의 모든 dp값이 저장된다.

마지막으로 L길이에 대한 dp값을 저장해야 되는데 이때

ch[left] == ch[right]라면 dp[left][right] = dp[left+1][right-1] + 1을 해준다.

이 의미는 길이 L에 대한 dp[left+1][right-1] 값과 ch[left], ch[right]를 부분집합으로 가지는 1개의 값을 더해주는 의미이다.

이렇게 이 문제를 O(n^2)에 해결 할 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

#include <iostream> #include <cstdio> #include <cstring>   #define MAX 1010   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];               if (ch[left] == ch[right])                 dp[left][right] += dp[left + 1][right - 1] + 1;         }     }       printf("%lld\n", dp[0][len - 1]);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus