[백준 1509] 팰린드롬 분할

문제 링크 : 1509번: 팰린드롬 분할 (acmicpc.net)

1509번: 팰린드롬 분할

 

다이나믹 프로그래밍 문제이다.

 

1. PAL[x][y] : [x, y] 에 속한 부분 문자열이 팰린드롬이면 true, 아니면 false 를 나타내도록 한다.

    이 부분은 다이나믹 프로그래밍을 통해 쉽게 구할 수 있다.

 

2. dp[x] : 인덱스 x 지점 까지의 최소 분할 갯수를 나타내도록 한다.

     dp[0] = 1 으로 채운 후 1 부터 (문자열 길이 - 1) 까지 dp 배열을 채워가도록 한다.

     다음과 같이 표현할 수 있겠다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define endl '\n'

using namespace std;

int dp[2501];
bool PAL[2501][2501], check[2501];
string S;

void set_palindrome() {
	// 1. Set a base case
	for (int i = 0; i < S.size(); i++) PAL[i][i] = true;
	for (int i = 0; i < S.size() - 1; i++) {
		if (S[i] == S[i + 1]) PAL[i][i + 1] = true;
		else PAL[i][i + 1] = false;
	}

	// 2. Dynamic Programming
	for (int gap = 2; gap < S.size(); gap++) {
		for (int i = 0; i < S.size() - gap; i++) {
			int j = i + gap;
			if (S[i] == S[j] && PAL[i + 1][j - 1]) PAL[i][j] = true;
			else PAL[i][j] = false;
		}
	}

	dp[0] = 1;
	for (int i = 1; i < S.size(); i++) {
		dp[i] = dp[i - 1] + 1;
		for (int j = 0; j < i; j++) {
			if (PAL[j][i]) dp[i] = min(dp[j - 1] + 1, dp[i]);
		}
	}

	cout << dp[S.size() - 1];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> S;
	set_palindrome();

	return 0;
}