longest Chunked palindrome list

Examples : 

Input : VOLVO 
Output : 3 
Explanation : 
(VO)L(VO) 


Input : merchant 
Output : 1 

Explanation : No chunks possible. 

Input : 

ghiabcdefhelloadamhelloabcdefghi 

Output : 7 

Explanation : 

(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)

------------------

최악의 경우

(abcde) 1 개는 보장된다.

최선의 경우

abcba >> n개가 보장

azcba >> 3개

(a)(zcb)(a)

일단 팰린드롬인 애는 그대로 포장할 수 있다. 포장해도 되는 애를 안해서 얻는 이득이 있나?

팰린드롬인 단어를 포장하지 않는 경우 갯수가 무조건 감소하거나 같게 되므로 이득이 없다는 것을 안다. 만약 팰린드롬인 단어를 포함해야만 다른 곳의 아수라장을 피할 수 있다면?

a(c)za(c)z

안되면 더 큰걸 잡아야지 "안됨" 이 되는게 아니라서, 이런 그리디 솔루션은 어렵다.

이렇게 답이 막히면 완전탐색부터 시작해 보자. DP로 비벼질 지도?

acbac >> a c 달라서 안됨! ac는 됨! 이걸로 묶어서 그 안에껄 재귀하자. 오 이거 되겠네. 디피문제구나.

리얼 완전탐색을 생각하니 디피로 풀리는구나. 막히면 완전탐색!

postfix = prefix 경우를 순회하면서 모두 찾는다. 각각의 경우에 대해 2 + 안쪽 재귀 결과값을 구해서 그 최솟값을 찾아준다.

아, 그리고 *** " 최솟값 " 이 나오면 DP 일 가능성이 매우 높다.

막히면 완전탐색..

막히면 완전탐색..

막히면 완전탐색..!!!!

!!!!!

int findminbrackets(string & s, index k){

// base case

if(k==s.size()/2) return 1;

string tmp(s.begin()+k,s.end()-k-1);

string cmp = tmp;

reverse(tmp.begin(),tmp.end());

if(cmp==tmp) return s.size()-2*k;

// general case, find postfix == prefix

int ret = 1;

for(int i = k+1 ; i <= s.size()-k; i++){

int j = i;

int l = k;

int flag = 0;

while(j<=s.size()-k){

if(s[l]==s[j]){

j++;

k++;

}else{

flag = 1;

break;

}

}

if(flag==1) continue;

// found a postfix==prefix

ret = max(ret,2+findminbrackets(s,s.size()-j+1));

}

return ret;

}

caching을 쓰면 결국에는 가능한 k의 값이 N개 뿐이고, 각 순회에 대해 O(N)의 행위를 하므로 O(N^2) 이다..!!