Boj 1509) 팰린드롬 분할

문제

백준 1509

설명

두 작업으로 이루어져 있다.

• 첫번째는 문자열의 일정 범위가 팰린드롬인지 상수시간 내에 구할 수 있도록 전처리를 하는 작업이다. 여기선 Mancher 알고리즘을 사용했지만 DP 를 사용해도 된다. Chk() 함수의 구현부만 달라질 문이다.
• 두번째는 최소 문자열 분할을 구하는 작업이다. DP 로 구한다.

여기서는 내가 헤메었던 두번째 작업에 대해 설명하려고 한다.

점화식 도출

	// dp2[i][j] => i 번째 인덱스에서 j 길이의 부분문자열이 최소 몇개로 분할이 되는지 저장
	// 현재 해당 부분문자열이 펠린드롬의 경우 1로 초기화 한 상태
	for (int len = 2; len <= n; len++)      // 길이가 2 인 부분문자열
		for (int i = 0; i <= n - len; i++)  // 가능한 모든 시작지점
			for (int j = 1; j < len; j++)   // 모든 경우에 대해 두 부분으로 쪼갬
				dp2[i][len] = min(dp2[i][len], dp2[i][j] + dp2[i+j][len-j]);

나는 처음에 위와 같은 코드를 생각했었다. 누가봐도 시간초과가 의심되는 삼중 반복문이다.

하지만 잘 생각해보면 dp2[i][j] + dp2[i+j][len-j] 부분은 중복되는 경우가 있다. dp2[i][j] 를 X 라고하고 dp2[i+j][len-j] 를 Y 라고 해보자. Y 가 만약 2개 이상의 팰린드롬으로 분해가 된다면 이는 문자열 A 와 펠린드롬인 B 로 쪼개질 수 있다. 그러면 X, Y 를 X+A, B 로 만들 수 있다. 위 코드의 마지막 반복문은 i 에서 시작하는 길이가 len 인 부분문자열을 쪼갤 수 있는 모든 경우를 셈하므로 우리가 새로 구성한 조합은 중복이 된다.

그럼 중복되는 경우를 지우는 방법이 뭐가 있을까? 간단한 방법은 문자열을 팰린드롬 + 나머지로 쪼개는 것이다. 그러면 임의의 시작점에 대해서도 dp 를 구할 필요가 없어져 시간복잡도가 O(\(\mathrm{N}^2\)) 가 된다.

그렇게해서 도출된 코드가 위 풀이코드이다.

시간 복잡도

O(\(\mathrm{N}^2\))

코드

const int MAXIN = 2501;
char in[MAXIN * 2]; int n;
int dp[MAXIN*2], dp2[MAXIN];

void Mancher()
{
	int r = 0, p = 0;
	for(int i = 0; i < n; i++)
	{
		if (i <= r)
			dp[i] = min(dp[p * 2 - i], r - i);
		else 
			dp[i] = 0;

        if(i + dp[i] >= r)
		while (i - dp[i] - 1 >= 0 && i + dp[i] + 1 < n && in[i - dp[i] - 1] == in[i + dp[i] + 1])
			dp[i]++;

		if (r <= i + dp[i])
		{
			r = i + dp[i];
			p = i;
		}
	}
}

// [s, e] 에서 팰린드롬인지 체크
inline bool Chk(int s, int e)
{
	return s == e || dp[s + e] >= e - s;
}

int main()
{
	scanf("%s", in); n = strlen(in);
	for (int i = n-1; i >= 0; i--) in[i<<1] = in[i];
	for (int i = 0; i < n-1; i++) in[(i<<1)+1] = '#';
	
	n = n * 2 - 1;
	Mancher();
	n = (n + 1) / 2;

	// 최소조합 구하기
	for (int len = 1; len <= n; len++)
	{
		dp2[len] = Chk(0, len-1) ? 1 : 1e9;
		for (int i = 1; i <= len; i++)
			if (Chk(len-i, len-1))
				dp2[len] = min(dp2[len], dp2[len - i] + 1);
	}

	cout << dp2[n];
}