[백준 C++] 1509번: 팰린드롬 분할

1. 문제

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

 

2. 알고리즘 분류

• 다이나믹 프로그래밍

 

3. 소스코드

#include <iostream>
#include <algorithm>
#include <string>
#define MAX_LEN 2501
#define INF 2134567890

using namespace std;

bool dp[MAX_LEN][MAX_LEN];
string str;
int str_len, result[MAX_LEN];

// 팰린드롬인지 확인하는 알고리즘
bool is_palindrome(int start, int end) {
	// end 값이 문자열 길이를 넘어갔을 경우, False
	if (end > str_len)
		return false;

	// 시작 문자열과 끝 문자열이 같고, 시작점과 끝점 문자열을 제외했을 때, 그 문자열이 팰린드롬일 경우, True
	if (str[start] == str[end] && (dp[start + 1][end - 1] || end - start == 1))
		return true;

	// 그 외는 False
	return false;
}

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

	// 문자열 입력
	cin >> str;

	str = " " + str;	
	str_len = str.length();

	// DP 알고리즘
	// dp[start][end] = start번째 ~ end번째 문자까지 문자열이 팰린드롬인지 True/False 
	for (int len = 0; len < str_len; len++) {
		for (int start = 1; start + len < str_len; start++) {
			if (len == 0)	// 문자열 길이가 1이면, 무조건 팰린드롬
				dp[start][start + len] = true;
			else if (is_palindrome(start, start + len))	// 팰린드롬인지 확인
				dp[start][start + len] = true;
		}
	}

	// 최소 분열 갯수 구하기
	result[0] = 0;
	for (int end = 1; end < str_len; end++) {
		result[end] = INF;	// INF 값으로 초기화

		for (int start = 1; start <= end; start++) {

			// 팰린드롬일 경우, (이전 문자열까지 최소 분열 갯수 + 1) 값 갱신
			if (dp[start][end])
				result[end] = min(result[end],result[start - 1] + 1);
		}
	}

	// 정답 출력
	cout << result[str_len - 1];

	return 0;
}

 

4. 유용한 알고리즘

 1) 다이나믹 프로그래밍(팰린드롬)

// 팰린드롬인지 확인하는 알고리즘
bool is_palindrome(int start, int end) {
	// end 값이 문자열 길이를 넘어갔을 경우, False
	if (end > str_len)
		return false;

	// 시작 문자열과 끝 문자열이 같고, 시작점과 끝점 문자열을 제외했을 때, 그 문자열이 팰린드롬일 경우, True
	if (str[start] == str[end] && (dp[start + 1][end - 1] || end - start == 1))
		return true;

	// 그 외는 False
	return false;
}

int main() {
	// DP 알고리즘
	// dp[start][end] = start번째 ~ end번째 문자까지 문자열이 팰린드롬인지 True/False 
	for (int len = 0; len < str_len; len++) {
		for (int start = 1; start + len < str_len; start++) {
			if (len == 0)	// 문자열 길이가 1이면, 무조건 팰린드롬
				dp[start][start + len] = true;
			else if (is_palindrome(start, start + len))	// 팰린드롬인지 확인
				dp[start][start + len] = true;
		}
	}

	return 0;
}