1509번: 팰린드롬 분할 - DP

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

1509번: 팰린드롬 분할

 

1. 팰린드롬의 시작과 끝을 전부 구한다. 본인은 이 정보를 palinEnd에 저장했다.

2. dp 계산

dp[i] : str index i에서 str 끝까지 팰린드롬 개수의 최소

dp[i] = min(dp[i], dp[palinEnd[i][ 0 ~ palinEnd[i].size()-1] ] ) + 1

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <string>
#define inf 1e9
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

string str;
vector<int> palinEnd[2500]; //i에서 시작하는 팰린드롬이 끝나는 index + 1
int dp[2500]; //i에서 str 끝까지 팰린드롬 개수의 최소

int solve(int idx)
{
	if (idx == str.length()) return 0;
	if (dp[idx] != inf) return dp[idx];

	for (int e : palinEnd[idx])
	{
		dp[idx] = min(dp[idx], solve(e));
	}
	dp[idx] += 1;
	return dp[idx];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> str;
	for (int i{ 0 }; i < str.length(); i++)
	{
		int l, r;

		l = i, r = i;
		while (l >= 0 && r < str.length())
		{
			if (str[l] == str[r])
			{
				palinEnd[l].push_back(r + 1);
				l--; r++;
			}
			else break;
		} //팰린드롬 길이가 홀수일 때

		l = i, r = i + 1;
		while (l >= 0 && r < str.length())
		{
			if (str[l] == str[r])
			{
				palinEnd[l].push_back(r + 1);
				l--; r++;
			}
			else break;
		} //팰린드롬 길이가 짝수일 때
	}

	fill(&dp[0], &dp[2500], inf); //초기화
	cout << solve(0);
}