[Baekjoon] 1509번: 팰린드롬 분할

🥅 문제

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

 

🔍 설계

부분 문자열들 중에서 어디서부터 어디까지 팰린드롬인지 먼저 구해야 한다. 팰린드롬을 구하는 방법은 다음과 같다.

 

문자 개수가 하나인 경우, 팰린드롬이다.

문자 개수가 2개인 경우, 두 문자가 같으면 팰린드롬이다.

문자 개수가 3개 이상인 경우, 맨 앞과 맨 뒤가 같고, 가운데가 팰린드롬이면, 팰린드롬이다.

 

이제 팰린드롬을 구했으니, 최소로 분할해야 한다. 최소 분할 수는 반복문으로 어떤 인덱스까지의 최소 분할 개수를 저장하면서, 구할 수 있다. 주의해야할 점은 팰린드롬이 기본적으로 성립해야 한다는 것이다.

 

기존에 저장된 값과 0부터 end 사이의 인덱스를 start라고 할 때, start부터 end까지 팰린드롬이 성립한다면, end까지의 팰린드롬 최소 분할 수는 기존값과 0~start-1까지의 분할 최소 수 + 1 중 최솟값이다.

 

👊 풀이

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

string str;
int len;
vector<vector<bool>> palindrome(2500, vector<bool>(2500, false));
vector<int> dp(2500, 1e9 + 7);

void make_palindrome() {
	for (int i = 0; i < len; i++) {
		palindrome[i][i] = true;
	}
	for (int i = 0; i < len - 1; i++) {
		if (str[i] == str[i + 1]) {
			palindrome[i][i + 1] = true;
		}
	}
	for (int diff = 2; diff < len; diff++) {
		for (int start = 0; start + diff < len; start++) {
			int end = start + diff;
			if ((str[start] == str[end]) && palindrome[start + 1][end - 1]) {
				palindrome[start][end] = true;
			}
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> str;
	len = str.length();

	make_palindrome();

	for (int end = 0; end < len; end++) {
		for (int start = 0; start <= end; start++) {
			if (palindrome[start][end] == true) {
				if (start == 0) {
					dp[end] = 1;
					continue;
				}
				dp[end] = min(dp[end], dp[start - 1] + 1);
			}
		}
	}

	cout << dp[len - 1] << "\n";

	return 0;
}