문제 풀이

d[31][31]을 선언하고 다이나믹 프로그래밍으로 문제를 풀이한다.
d[i][j] (인덱스 i부터 j까지 팰린드롬이 되는 부분 수열의 개수) 라고 생각했을 때
길이가 1인 문자열은 팰린드롬이고
길이가 2인 문자열은 팰린드롬이 2개 또는 3개(ab와 같이 문자가 다른경우 2개, aa와 같이 문자가 같은경우 3개)

길이 3부터는 d[i][j] = d[i+1][j] + d[i][j-1] - d[i+1][j-1] 을 적용 (중복되는 부분을 빼줌)
단, i번째 문자와 j번째 문자가 같은경우 가운데 중복되는 팰린드롬과 양끝의 문자를 통해 새로운 팰린드롬을 만들 수 있으므로 빼지 않고 +1을 해준다.(예를들어 i=0, j=3일 때, "abca" -> aba, aca, aa)

문제 링크

boj/17182

소스코드

PS/17182.cpp

#include <string>
#include <vector>
#include<iostream>
#include<memory.h>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;

long long d[31][31];
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	string s;
	cin >> s;
	int len = s.size();
	for (int i = 0; i < len; i++)
	{
		d[i][i] = 1;
		if (i+1<len && s[i] == s[i + 1])
			d[i][i + 1] = 3;
		else if(i+1<len)
			d[i][i + 1] = 2;
	}
	for (int i = 2; i < len; i++)
	{
		for (int j = 0; j < len; j++)
		{
			int k = j + i;
			if (k >= len)
				break;
			if (s[j] == s[k])
				d[j][k] = d[j+1][k] + d[j][k-1]  + 1;
			else
				d[j][k] = d[j + 1][k] + d[j][k - 1] - d[j + 1][k - 1];
		}
	}
	cout << d[0][len - 1];
}