[백준 알고리즘] 1509번 팰린드롬 분할 c++

문제를 보자마자 dp를 적용해서 풀어야겠다고 느꼈으나

아직 dp로 푸는건 너무 오래걸리는 것 같다. 분발하자.

 

 

 

dp 테이블의 [i ,j]의 원소 값은 i에서 j까지 분할을 했을 때

펠린드롬 분할이 가능하면 true, 불가능하면 false이다.

(따라서 테이블에서 i<=j인 부분만 사용)

 

dp테이블을 순차적으로 채우는 과정은 다음과 같다.

 

1. i=j일때 dp테이블은 true (길이가 1이면 펠린드롬)

 

2. i+1=j일때 s[i] = s[j]이면 dp테이블은 true (길이가 2일때 두 원소가 같으면 펠린드롬)

 

3. 길이가 2~문자열길이(n)일때 순차적으로 탐색했을 때,

j = i+n일때 s[i] = s[j]이면서 dp[i+1][j-1]이 true면

dp[i][j]는 true

 

ex) ABBA라는 문자열에서 2번 과정으로 i=1, j=2일때 dp가 true이고

i=0, j=3일때 s[0]과 s[3]은 A로 값이 동일하고 dp[1][2]도 true이므로

dp[0][3]도 true이다

 

 

dp테이블을 모두 채운 후, 

각 길이에서 최소의 팰린드롬 분할의 수를 저장하는 d배열을 순차적으로 채우면

원하는 결과를 d[문자열길이]에 얻을 수 있다.

d배열은 dp테이블을 순차적으로 탐색하여 과

d[j] +1 와 dp[i][j]가 true일 때 d[i]+1들 중 최소를 d[i]로 한다.

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool dp[2501][2501];

int main(){
	string s;

	cin >> s;

	for(int i=0; i<s.size(); i++){
		dp[i][i] = true;
	}

	for(int i=0; i<s.size()-1; i++){
		if(s[i] == s[i+1])
			dp[i][i+1] = true;
	}

	for(int n = 2; n < s.size(); n++){
		for(int i=0; i< s.size()-n; i++){
			int j=i+n;
			if(s[i] == s[j] && dp[i+1][j-1]){
				dp[i][j] = true;
			}
		}
	}

	int d[2501];
	d[0] = 0;

	for(int n=1; n<=s.size(); n++){
		int j = n-1;
		d[n] = d[j] + 1;
		for(int i=0; i<n-1; i++){
			if(dp[i][j]){
				if(d[n] > d[i] + 1)
					d[n] = d[i] +1;
			}
		}
	}

	cout << d[s.size()] << endl;
	return 0;
}