[BOJ] 백준 1509번: 팰린드롬 분할

Class 5에는 대부분 DP로 구성된 것 같네요

recv(i)를 i번째 문자부터 시작했을때 가능한 최소 팰린드롬 수 DP[i]를 찾는 함수로 정하면

i <= j < n (문자열 길이) 인 j에 대하여 i~j가 팰린드롬이면 dp[i] = min(recv(j+1)+1,dp[i]) 입니다.

O(n^2) 풀이법으로 2500*2500에 대하여 1초안에 충분히 통과합니다.

 

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <memory.h>
#include <string>
#include <algorithm>

using namespace std;
int dp[2501];
string str;
int n;
int pal[2501][2501];

int ispal(int s, int e) {
	if (s >= e) {
		return pal[s][e] = 1;
	}
	int& ret = pal[s][e];
	if (~ret) return ret;
	ret = 0;
	if (str[s] == str[e]) {
		return ret = ispal(s + 1, e - 1);
	}
	return ret;
}
int recv(int node) {
	if (node == n) {
		return 0;
	}
	int& ret = dp[node];
	if (~ret) return ret;
	ret = 2e9;
	for (int i = node; i < n; i++) {
		if (ispal(node, i)) {
			ret = min(ret, 1 + recv(i+1));
		}
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(pal, -1, sizeof(pal));
	memset(dp, -1, sizeof(dp));
	cin >> str;
	n = str.length();
	cout << recv(0);
}