분할

문제 링크 (2026/4/7 기준) Gold I 문제 읽기 알파벳 대문자로만 이루어진 문자열 $S$가 주어집니다. $S$를 최소 개수의 팰린드롬을 분할할 때, 최소 분할 개수를 구해봅시다. 풀이 $|S|$가 최대 $2 , 500$으로, 생각보다 작습니다. $\mathcal{O}(|S|^2)$풀이를 생각해봅시다. 먼저, 팰린드롬 문자열이 애초에 어떻게 이루어지는지 고민해봅시다. $\Sigma = \lbrace \texttt{A}, \texttt{B}, \cdots, \texttt{Z} \rbrace$에 대해, $$ T \rightarrow \varepsilon \mid a \mid aTa \quad (a \in \Sigma) $$ 로 정의할 수 있습니다. 뭔 소리냐? 팰린드롬은 길이가 $0$ 또는 $1$인 문자열의 양 끝에 같은 문자를 하나씩 $0$회 이상 재귀적으로 붙인 꼴이라는 것입니다....