문제 풀러가기

Problem

• 처음엔 어떤 문자열을 팰린드롬으로 분할하여 나타낼 수 있는 집합의 경우의 수를 묻는 문제로
  착각하였다. 그러나 최소 몇 개의 팰린드롬으로 문자열을 표현할 수 있는 지를 묻는 문제였다.
  문자열이 ABACABA인 경우 답은 1이다.

Solution

• 분할된 팰린드롬의 길이가 길어야 분할의 횟수를 최소로 만들 수 있을 것이다.
• 어떤 문자열 S의 substring 팰린드롬 여부를 Brute Force로 확인하려면 O(N3)
  Memoization을 이용하면 시간 복잡도는 O(N2)이다. 즉 cache[start][end]
  배열로 S[start : end-1]의 팰린드롬 여부를 저장한다.
• 어떤 substring이 팰린드롬이고 마지막 index가 i일때 i+1에서 시작하는
  팰린드롬 substring을 찾는 과정을 반복한다. 이 과정을 반복하며 팰린드롬의
  개수를 카운트하고 최솟값을 찾는다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

int cache[2501][2501];
int dp[2501];
string str;
// 문자열의 start ~ (end - 1) Palindrome Check 
int isPalindrome(int start, int end){
	int& ret = cache[start][end];
	if(ret != -1) return ret;
	
	int len = (end - start) / 2;
	for(int i=0; i<len; i++){
		if(str[start + i] != str[end - 1 - i])
			return ret = 0;
	}
	return ret = 1;
}
// Palindrome의 집합으로 문자열을 표현하고 그 개수의 최솟값을 구한다.
int solve(int start){
	int len = str.length();
	int& ret = dp[start];
	if(ret != -1) return ret;
	if(start == len) return ret = 0;
	
	int mins = 10000;
	for(int i=start + 1; i<=len; i++)
		if(isPalindrome(start, i)){
			mins = min(mins, solve(i) + 1);
		}
	return ret = mins;
}

int main(){
	char s[2501];
	scanf("%s", s);
	str = s;
	
	memset(cache, -1, sizeof(cache));
	memset(dp, -1, sizeof(dp));
	int mins = solve(0);
	
	printf("%d \n", mins);
}

Result

• 위의 코드중 solve함수에서 memoization을 쓰지 않아 시간초과가 발생하였다.