[BOJ] 1509 팰린드롬 분할

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

1509번: 팰린드롬 분할

알고리즘: DP

 

시간복잡도: O(N^2)

 

접근:

1. 팰린드롬 문자열

-> 팰린드롬 문자는 부분 문제의 속성을 지녔기 때문에 Dynamic 으로 접근하기가 용이함.

2. (특정 규칙을 가지고) 분할 및 개수 구하기

-> 이 부분도 Dynamic 속성을 응용하기 쉽다. 예를 들어, D[i]: 0~i까지 분할(그룹)의 개수 라고 두면

    D[i] = D[i-1] + 1 (규칙을 만족하지 않아 새로운 그룹을 만들 시)

            D[i-1]       (규칙을 만족하여 이전 그룹에 속할 시)

    이런식으로 계산이 가능하기 때문이다.

 

ex)

ABACABA에서 가운데(C) 기준으로 팰린드롬 문자열을 찾아보면,

{A,B, ACA, B,A}, {A, BACAB, A}, {ABACABA} 

이런식으로 가장 긴 팰린드롬은 작은 팰린드롬들로 구성되어 있다는 것을 알 수 있다.

 

 

D[i]: i번째 문자까지 팰린드롬 분할의 개수

이렇게 두고 i번째 문자에서 좌우로 문자열을 확인하면서 팰린드롬인지 확인하고 DP 배열을 채워나갔다.

 

차례대로 코드의 점화식 부분을 설명하자면,

1. D[i] = Min(D[i], D[i-1]+1) : i번째 문자가 팰린드롬에 속하지 않을 시, 새로운 그룹 형성

2. D[i+j] = Min(D[i+j], D[i-j-1]+1) : i를 기준으로 (i-j)~(i+j)가 팰린드롬을 형성 (홀수 길이: ABA)

3. D[i+j] = Min(D[i+j], D[i-j] + 1) : i를 기준으로  (i-j+1)~(i+j)가 팰린드롬을 형성 (짝수 길이: ABBA)

 

 

// 1509 팰린드롬 분할

#include<iostream>
#include<cstring>
#define MIN(a, b) (((a)>(b))?(b):(a))
using namespace std;

int D[2501], l, j;
char s[2501];
int main()
{
	cin >> s;
	l = strlen(s);
	
	D[0] = 1;
	for (int i = 1; i < l; i++) 
		D[i] = 0x7fffffff;
	
	for (int i = 0; i < l; i++)
	{
		D[i] = MIN(D[i], D[i-1] + 1);
		j = 1;
		while (i-j >= 0 && i+j < l)		// ABA
		{
			if (s[i-j] != s[i+j]) break;
			D[i+j] = MIN(D[i+j], D[i-j-1]+1);
			j++;
		}
		j = 1;
		while (i-j+1 >= 0 && i+j < l)   // AA
		{
			if (s[i-j+1] != s[i+j]) break;
			D[i+j] = MIN(D[i+j], D[i-j]+1);
			j++;
		}
	}
	cout << D[l-1];
	return 0;
}

 

 

---

메모리를 추가로 사용하여 (N^2)

팰린드롬인지 여부를 확인하는 DP 배열을 미리 만들어서 써먹을 수도 있다. 

ex) P[i][j] : i~j가 팰린드롬인지 여부 (1: 팰린드롬, 0: 팰린드롬X)

 

for (i = 0 ~ N-1)

    D[i] = Min(D[i], D[i-1]+1)

    for (j = 0 ~ i-1)

        if (P[i][j] == 0) continue

            D[i] = Min(D[i], D[j-1]+1)