[백준 C++] 1509 팰린드롬 분할 - 다이나믹프로그래밍

1509번: 팰린드롬 분할

---

 

문제풀이

 

2차원 배열에 i 번째 문자부터 j 번째 문자까지의 부분 문자열이 팰린드롬인지 판별해서 저장해준 다음,

DP[k]에 0 번째 문자부터 k 번째 문자까지의 팰린드롬 분할 수의 최소값을 저장해주어 푸는 문제입니다.

 

팰린드롬 판별은 i번 문자와 j번 문자가 같고, i+1번~j-1번 문자열이 팰린드롬이면, i번~j번 문자열 또한 팰린드롬임을 알 수 있습니다.

---

코드

#include <iostream>
#include <string>
using namespace std;

bool Pal[2500][2500];
int DP[2500];

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

	string Str;
	cin >> Str;

	int Size = Str.length();
	for (int d = 0; d < Size; ++d)
	{
		for (int i = 0; i + d < Size; ++i)
		{
			if (d == 0)
			{
				Pal[i][i + d] = true;
				continue;
			}

			if (Str[i] == Str[i + d]
				&& (d == 1 || Pal[i + 1][i + d - 1]))
			{
				Pal[i][i + d] = true;
			}
		}
	}

	for (int i = 0; i < Size; ++i)
	{
		DP[i] = 2500;
		for (int j = 0; j <= i; ++j)
		{
			if (Pal[j][i])
			{
				if (j == 0)
				{
					DP[i] = 1;
					break;
				}
				else
				{
					DP[i] = min(DP[i], DP[j - 1] + 1);
				}
			}
		}
	}

	cout << DP[Size - 1];
}