[백준 2079, 1509] 팰린드롬 / 팰린드롬 분할 (C++)

[팰린드롬] 문제 링크: https://www.acmicpc.net/problem/2079

2079번: 팰린드롬

[팰린드롬 분할]문제 링크: https://www.acmicpc.net/problem/1509

1509번: 팰린드롬 분할

1. 주의할 점

- 두 문제 모두 최소의 팰린드롬 수를 구하는 문제지만 문자열의 길이가 다르다.

- 각 부분 문자열마다 비교할 때(구현 과정) 헷갈릴 수 있다.

 

2. 구현

- 길이가 1인 문자열 혹은 부분 문자열은 항상 펠린드롬이다 -> DP[i][i] = True

- 길이가 2인 문자열 혹은 부분 문자열은 오른쪽과 비교해서 같으면 펠린드롬이다 if(Str[i]==Str[i+1]) DP[i][i+1] = DP[i+1][i] = True

- 이 문제의 경우 2개의 배열 DP[][], Result[]가 필요하다.

DP[i][j] : Str[i] ~ Str[j]의 부분문자열이 팰린드롬인지 아닌지 알려주는 Boolean 배열

Result[i] : Str[1]~Str[i]의 부분문자열에 존재하는 최소 팰린드롬 개수

- Palindrome 함수:  문자열의 양옆 글자가 같고, 양옆 글자를 제외한 부분문자열이 팰린드롬이라면 해당 문자열은 팰린드롬이다

Ex) Str = "4321234"

양 끝 문자 : '4' == '4'    -> 같다

양 끝을 제외한 부분 문자열 = "32123"    -> 팰린드롬이다

결론: Str은 팰린드롬이다

- 이후 Result의 1번째 Index에서 Str의 길이까지 Result배열을 비교하면서 Result[Index]가 0이거나(아직 비교를 안한 경우), Result[Index] > Result[Index-1]+1를 만족하는 경우(현재 저장된 값보다 더 개수의 펠린드롬으로 Str[1]~Str[Index]까지의 문자열을 만들 수 있는 경우) Result[Index] = Result[Index]+1로 설정한다.

 

#include <iostream>
#include <string>
using namespace std;
bool dp[2501][2501] = { false, };
int result[2501];
string str;

void palindrome() {
	for (int i = 2; i < str.size(); i++) 
		for (int j = 1; j < str.size() - i; j++) 
			if (str[j] == str[j + i] && dp[j + 1][j + i - 1]) 
				dp[j][j + i] = dp[j + i][j] = true;	
}

int main() {
	cin >> str;
	str = " " + str;
	//길이 1개짜리는 항상 펠린드롬
	for (int i = 1; i <= str.size(); i++) 
		dp[i][i] = true;
	//바로 옆에 칸과 같다면 펠린드롬
	for (int i = 1; i < str.size(); i++) {
		if (str[i] == str[i + 1]) {
			dp[i][i + 1] = true;
			dp[i + 1][i] = true;
		}
	}
	palindrome();
	for (int i = 1; i <= str.size(); i++) {
		for (int j = 1; j <= i; j++) {
			if (dp[i][j]) {
				if (result[i] == 0 || result[i] > result[j - 1] + 1)
					result[i] = result[j - 1] + 1;
			}
		}
	}
	cout << result[str.size()-1];
	system("pause");
	return 0;
}