BOJ 1509 - 팰린드롬 분할 (dp)

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

 

https://suuntree.tistory.com/109

여기서 리뷰한 팰린드롬?을 이용해서 풀 것임.

 

<문제설명>

최대 2500자의 문자열이 주어진다. 이를 팰린드롬 부분수열로 집합을 만들 때, 그 집합의 크기가 최소가 되도록 묶는 경우의 수를 구하는 문제.

 

<풀이>

f(i) : i번째 이후의 문자열의 팰린드롬 부분수열로 집합을 만들 때, 집합의 최소 크기

f(i) = min( f(가능한 j값+1) + 1 )  단,  ( i<=j<=n-1, i~j번 부분수열은 팰린드롬)

 

모든 가능한 j값에 대해 최소값을 업데이트 해줘야 한다.

 

<코드>

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int IMP = 1e9;

string a;
int n, c[2501][2501], d[2501];

int isP(int i, int j) {
	int& ret = c[i][j];
	if (ret != -1) return ret;

	if (i == j) return ret = 1;
	if (i + 1 == j) return ret = (a[i] == a[j]);
	return ret = ((a[i] == a[j]) && (isP(i + 1, j - 1)==1));
}

//k번째 이후의 문자열을 가지고 분할할 수 있는 팰린드롬 부분집합의 최소값
int f(int k) {
	//의미상 불가능하지만, 계산의 통일성을 위한 문장
	if (k == n) return 0;

	int& ret = d[k];
	if (ret != -1) return ret;

	ret = IMP;
	for (int j = k; j < n; j++) 
		if (isP(k, j)) 
			ret = min(ret, f(j+1) + 1);
		
	return ret;
}

int main() {
	cin >> a;
	n = a.size();

	fill(&c[0][0], &c[2500][2501], -1);
	fill(d, d+2501, -1);

	cout << f(0) << '\n';
}