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

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

1509번: 팰린드롬 분할

 

문제

---

 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.

분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 문자열이 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있고, 최대 길이는 2,500이다.

 

출력

---

첫째 줄에 팰린드롬 분할의 개수의 최솟값을 출력한다.

 

 

문제 풀이

---

2차원 배열을 이용하는 dp 문제.

팰린드롬인지 아닌지를 판단하는 2차원 배열을 만드는데, 배열[i][j]는 j번째 index의 문자로 시작하고 i번째 index의 문자로 끝나는 문자열의 팰린드롬 여부를 저장한다고 정의한다.

길이 1짜리 문자열은 팰린드롬이다. 따라서 배열[i][i]에는 true가 저장된다.

길이 1이 아닌 어떤 문자열 ij가 팰린드롬이라면 첫번째 문자와 마지막 문자가 같아야 하고, 첫번째 문자와 마지막 문자를 제외한 나머지 역시 팰린드롬이어야 한다. 나머지 길이가 팰린드롬이 아니라면 ij역시 팰린드롬이 될 수 없다. 따라서 첫번째 문자와 마지막 문자가 같다면 [i][j] = [i-1][j+1]이 성립한다. 첫번째 문자와 마지막 문자가 같지 않다면 당연히 팰린드롬이 아니므로 false를 저장한다.

 

i가 0일 때, 문자열의 길이가 1이므로 팰린드롬이고, 분할 최수 개수는 1이다.

i가 1부터는 시작 index가 0부터 i까지 팰린드롬인지 아닌지를 확인한다. 문자열 처음부터 i번째까지 분할할 수 있는 최대 개수는 1씩 자르는 i+1개이지만, 만약 특정 index j부터 index i까지 팰린드롬이라면 해당 문자열로 분할해 분할의 개수를 줄일 수 있다. 이때 분할의 개수는 j-1번째 문자까지의 분할의 최수 개수 + 1이 된다.

반복문을 돌리면서 i번째 index까지의 팰린드롬인 경우가 여러가지 생길 수 있고, 그 중 분할의 최소의 개수를 구해야 하므로 min()함수를 통해 i번째 index까지의 현재 분할 최솟값과 비교하여 최솟값을 찾는다.

 

아래는 문자열 DABADD를 예시로 들었다.

아래는 코드.

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	string str;
	cin >> str;
	int N = str.length();
	bool** isPalindrome = new bool*[N];
	int* length = new int[N];
	for (int i = 0; i < N; i++)
	{
		isPalindrome[i] = new bool[N];
		for (int j = 0; j < N; j++)
		{
			if (i == j)
			{
				isPalindrome[i][j] = true;
			}
			else
			{
				isPalindrome[i][j] = false;
			}
		}
	}
	length[0] = 1;
	for (int i = 1; i < N; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (str[i] == str[j])
			{
				if (i - j == 1)
				{
					isPalindrome[i][j] = true;
				}
				else
				{
					isPalindrome[i][j] = isPalindrome[i -  1][j + 1];
				}
			}
			else
			{
				isPalindrome[i][j] = false;
			}
		}
	}
	for (int i = 1; i < N; i++)
	{
		bool canFound = false;
		length[i] = 100000;
		for (int j = 0; j <= i; j++)
		{
			if (isPalindrome[i][j] == true)
			{
				if (j == 0)
				{
					length[i] = 1;
				}
				else
				{
					length[i] = min(length[i], length[j - 1] + 1);
				}
			}
		}
	}
	cout << length[N - 1] << "\n";
	return 0;
}