팰린드롬 분할
시간 제한2초메모리 제한128 MB
대문자 문자열(길이 2500 이하)을 팰린드롬 부분 문자열들로 나눌 때 필요한 최소 조각 수를 구합니다.
문제
주어진 문자열을 여러 개의 팰린드롬 부분 문자열로 나누려고 한다. 예를 들어 ABACABA는 {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}처럼 나눌 수 있다.
문자열 전체를 팰린드롬 조각들로 나눌 때 필요한 조각 수의 최솟값을 구하라.
입력
첫째 줄에 알파벳 대문자로만 이루어진 문자열이 주어진다. 문자열의 길이는 최대 2,500이다.
출력
첫째 줄에 팰린드롬 분할에 필요한 조각 수의 최솟값을 출력한다.