[ 백준 13330 ] 유사 팰린드롬 : C++ 풀이

소스 코드

#include<iostream>
using namespace std;

int n, k, l;
string input;

int u[10001][10001];
int dp[10001]; // 유사 펠린드롬의 여부 = 1 이상이면 해당, 또 1 이상인 값이 여러개 일 경우 가장 적은 값 입니다.

int getU(int s, int e) {
	if (s >= e) return 0;
	if (u[s][e]) return u[s][e];
	if (input[s] != input[e]) return 0;
	return u[s][e] = 1 + getU(s + 1, e - 1);
}

bool is_theta(int s, int e) {
	if (s == e) return false;

	int len = e - s + 1;
	int v_len = getU(s, e);

	if (k*len <= 2 * v_len * l) return true;
	return false;
}

int main() {
	cin >> n >> k >> l >> input;

	for (int i = 0; i < n; ++i) {
		dp[i] = -1;

		if (is_theta(0, i)) dp[i] = 1;

		for (int j = 1; j < i; ++j) {
			// 끝점이 i인 경우를 모두 검색하다보면 dp 값을 한번만 방문할 수 있을 것이다.
			// 1 ~ j / j + 1 ~ i 이렇게 두개로 나눔.
			// 더 작은 segment로 나뉠 수 있는 것 아닌가? -> 그 경우는 이미 dp[a][b] : b가 i보다 작은 경우에서 모두 구했음.
			if (is_theta(j, i) && dp[j - 1] > 0) {
				if (dp[i] > 1 + dp[j - 1] || dp[i] == -1) {
					
					dp[i] = dp[j - 1] + 1;
				}
			}
		}
	}
	
	cout << ((dp[n - 1] == -1) ? 0 : dp[n - 1]);
}