[BAE/<JOON> 문제풀이] 1509. 팰린드롬 분할

www.acmicpc.net/problem/1509

1509번: 팰린드롬 분할

Manacher's 알고리즘을 사용해 문자열 내부에 있는 모든 팰린드롬의 길이를 구할 수 있다.

 

최소 분할 수를 구하는 점화식은 다음과 같다.

 

현재 위치 팰린드롬 길이 k에 대해서

dp[i] = min(dp[i - 1] + 1, dp[i])

-> 현재 위치의 팰린드롬을 사용하는 것보다 사용하지 않는 것이 더 짧은 경우

 

for(1 ~ k = j) dp[i + j] = min(dp[i + j], dp[i - j - 1])

-> 현재 위치의 팰린드롬을 사용하는 것이 더 짧은 경우

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int dp[5005];

int main()
{
	string s;
	cin >> s;
	string arr = "#";
	for (char v : s) {
		arr += v;
		arr += '#';
	}
	int n = arr.length();
	int r = 0, p = 0;
	for (int i = 0; i < n; i++) {
		if (i <= r) {
			dp[i] = min(dp[2 * p - i], r - i);
		}
		else {
			dp[i] = 0;
		}

		while (i - dp[i] - 1 >= 0 && i + dp[i] + 1 < n) {
			if (arr[i - dp[i] - 1] == arr[i + dp[i] + 1]) dp[i]++;
			else break;
		}

		if (r < i + dp[i]) {
			r = i + dp[i];
			p = i;
		}
	}	

	vector<int> dp2(n + 1, 5005);
	dp2[0] = 0;
	for (int i = 1; i <= n; i++) {
		if (arr[i] == '#' && dp[i] == 0) {
			dp2[i] = dp2[i - 1];
			continue;
		}

		dp2[i] = dp2[i] < dp2[i - 1] + 1 ? dp2[i] : dp2[i - 1] + 1;

		for (int j = 1; j <= dp[i]; j++) {
			int idxb = i - j - 1;
			int idxf = i + j;
			if (idxb < 0) {
				dp2[idxf] = 1;
				continue;
			}
			dp2[idxf] = dp2[idxf] < dp2[idxb] + 1 ? dp2[idxf] : dp2[idxb] + 1;
		}
	}

	/*for (int i = 1; i <= n; i++) {
		cout << dp2[i] << " ";
	}*/

	cout << dp2[n - 1];

	return 0;
}