Boj 1509 팰린드롬 분할 C++

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

문자열이 주어지고, 순서를 유지하며 모든 원소가 팰린드롬임을 유지할 때 최소 원소 개수를 구한다.

문자열의 길이는 최대 2500이므로 제곱 정도까지 돌 수 있다.

어디서 분할할 지 잡고, 팰린드롬임을 판정하면 오래 걸릴 것 같다. 팰린드롬 판정은 길이만큼 걸리므로, 빠르게 할 수 있는 방법이 필요하다. 이 방법은 이미 사용해본 적이 있을 것이다.

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

위의 방법으로 팰린드롬을 판정하면 전처리 O(N²)에 확인에 O(1)이므로 구간 팰린드롬 확인을 빠르게 처리할 수 있다.

이제 분할할 곳을 어떻게 정할지 생각해봐야 한다.

dp[i] : 문자열의 i 번째까지 봤을 때 최소 원소 개수

로 테이블을 정의할 수 있겠다.