문제 링크
(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$회 이상 재귀적으로 붙인 꼴이라는 것입니다.

$\textrm{DP}_ i$를 $S$의 $i$번째 문자까지 고려했을 때의 최소 분할 개수라고 정의합시다. 초기 DP 배열을 $\textrm{DP} = [\textrm{INF}, \textrm{INF}, \cdots, \textrm{INF}]$로 두고, 편의상 $S_ 0 = \varepsilon$으로 약속하고 $\textrm{DP}_0 = 0$으로 base case를 채웁시다.

이제부터 $i=1$부터 $|S|$까지 순서대로 돌면서 DP 테이블을 갱신해 봅시다.

홀수 길이 팰린드롬

$S$의 부분 문자열 $S_i$가 어떤 홀수 길이 팰린드롬 문자열의 중심이라고 합시다. 당연하게도 문자열 $S_i$는 길이가 $1$인 팰린드롬 문자열이므로, $\textrm{DP}_ {i}$의 후보는 우선 $\textrm{DP}_ {i - 1} + 1$이 됩니다. 여기서 답의 상한이 $|S|$라는 사실도 관찰할 수 있습니다.

부분 문자열 $S_i$가 팰린드롬이라면, $$ S_{i-1} S_i S_{i+1}, \newline S_{i-2} S_{i-1} S_i S_{i+1} S_{i+2}, \newline \vdots $$ 등의 문자열이 팰린드롬의 후보가 됩니다. 여기서 처음으로 팰린드롬이 깨지게 된다면, 이후는 당연히 팰린드롬이 아니므로 더 볼 필요가 없습니다.

$j = 0$에서부터 $1$씩 키워가며 $S_{i-j} S_{i-j+1}\ldots S_{i+j-1} S_{i+j}$가 팰린드롬인지 판정하며 순회하면서 $\textrm{DP}_ {i+j} \leftarrow \min(\textrm{DP}_ {i+j}, \textrm{DP}_{i-j-1} + 1)$로 갱신합시다.

아까 정의한 DP 점화식의 정의에 의해, $\textrm{DP}_{i-j-1}$는 이 시점에서 분명히 $S$의 $i-j-1$번째 문자까지 고려했을 때의 최소 분할의 개수입니다.

점화식이 갱신되는 방향은 $0 \le i < j \le |S|$인 $i$, $j$에 대하여, $\textrm{DP}_i \rightarrow \textrm{DP}_j$와 같이, 업데이트가 자기보다 작은 인덱스에서 시작되는 전이만 일어나기 때문에, 갱신되는 순서가 꼬이지 않습니다.

짝수 길이 팰린드롬

$S$의 부분 문자열 $S_i S_{i+1}$이 어떤 짝수 길이 팰린드롬 문자열의 중심이라고 합시다.

$S_i S_{i+1}$가 팰린드롬이라면, $$ S_{i-1} S_i S_{i+1} S_{i+2}, \newline S_{i-2} S_{i-1} S_i S_{i+1} S_{i+2} S_{i+3}, \newline \vdots $$ 등이 팰린드롬의 후보가 됩니다. 마찬가지로 처음으로 팰린드롬이 깨지게 된다면, 그 이후는 더 볼 필요가 없습니다.

홀수 팰린드롬과 마찬가지로 $j = 0$에서부터 $1$씩 키워가며 $S_{i-j} S_{i-j+1}\ldots S_{i+j} S_{i+j+1}$이 팰린드롬인지 판정하며 순회하면서 $\textrm{DP}_ {i+j+1} \leftarrow \min(\textrm{DP}_ {i+j+1}, \textrm{DP}_ {i-j-1} + 1)$로 갱신합시다.

코드

#![allow(unused_imports, dead_code)]
use std::{cmp::{max, min, Reverse}, collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}, f64::consts::PI, fmt::{format, Write}, fs::read, io::{stdin, Read}, mem::{swap, self}, str::SplitWhitespace, usize, vec};
 
fn main() {
    let mut buf = String::new();
    let mut out = String::new();
 
    stdin().read_to_string(&mut buf).unwrap();
    let mut scan = Scanner::new(buf.split_whitespace());

    let mut tc = 1;
    if tc != 1 { tc = scan.next::<usize>(); }
    for i in 0..tc {
        solve(&mut scan, &mut out, i);
    }
    print!("{out}");
}

fn solve<'a>(scan: &mut Scanner<'a, SplitWhitespace<'a>>, out: &mut String, _tc: usize) {
    let s = scan.next::<String>().into_bytes();
    let n: usize = s.len();
    let mut a = vec![0u8; n + 1];
    for i in 1..=n { a[i] = s[i - 1]; }
    
    let mut dp = vec![1234567890; n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for i in 1..=n {
        dp[i] = min(dp[i - 1] + 1, dp[i]);
        for j in 0..min(i, n - i + 1) {
            if a[i - j] != a[i + j] { break; }
            dp[i + j] = min(dp[i + j], dp[i - j - 1] + 1);
        }

        for j in 0..min(i, n - i) {
            if a[i - j] != a[i + j + 1] { break; }
            dp[i + j + 1] = min(dp[i + j + 1], dp[i - j - 1] + 1);
        }
    }
    
    writeln!(out, "{}", dp[n]).unwrap();
}

struct Scanner<'a, I: Iterator<Item = &'a str>> {
    iter: I,
}
 
impl<'a, I: Iterator<Item = &'a str>> Scanner<'a, I> {
    fn new(from: I) -> Self {
        Self { iter: from }
    }
    fn next<T: std::str::FromStr>(&mut self) -> T {
        self.iter.next().unwrap().parse().ok().unwrap()
    }
}

생각보다 점화식이 간단하게 나오고, DP 테이블을 채우기도 어렵지 않습니다.

후기

골드 1치고 생각보다 쉽게 풀리길래 solved.ac 기여창을 보니, 팰린드롬을 전처리한다는 아이디어로 풀었다는 기여가 대부분이었습니다. 궁금해서 구글에 검색해보니 상단에 뜨는 많은 블로그가 그런 풀이로 설명한 것 같은데, 생각보다 더 쉬운 풀이가 있어서 공유하는 차원에서 글을 작성합니다.