BOJ 1509 팰린드롬 분할

주어진 문자열을 팰린드롬인 문자열 여러개로 분할하는데, 분할되는 문자열의 최대 개수는 문자 하나 하나씩으로 분할할 때 나올 것이다. 하지만 이 문제에서는 최소 개수를 구해야 한다.

d[n]=n번째 문자부터 시작해서 문자열을 묶어보고 분할할 때, 팰린드롬 분할의 최소 개수
d[n] = min(m은 한 묶음이 되는 문자열의 길이 1에서 N-n까지... | d[n+m]+1)
이렇게 하면 O(N^2)의 시간복잡도가 나오는...게 아니라 각 묶음에 대해서 팰린드롬인지 검사해야 하므로 O(N)만에 검사하면 O(N^3)이 나오게 될 것이다. 시간초과다. 그럼 dp를 이용하면 팰린드롬인지 판단하는데 처음에 O(N^2)만큼 걸리고 그 이후로는 O(1)만에 팰린드롬인지 판단 가능하므로 결국 O(N^2+N^2)의 시간복잡도를 가지게 될 것이다.

구현해 봐야겠다. AC를 받았다.