문제 링크
(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 $$ 등의 문자열이 팰린드롬의 후보가 됩니다. 여기서 처음으로 팰린드롬이 깨지게 된다면, 이후는 당연히 팰린드롬이 아니므로 더 볼 필요가 없습니다.

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

이 이터레이션에서 점화식이 갱신되는 방향은 $0 \le j < i \le |S|$인 $i$, $j$에 대하여, $\textrm{DP}_j \rightarrow \textrm{DP}_i$와 같이, 업데이트가 자기보다 작은 인덱스에서 시작되는 전이만 일어나기 때문에, 갱신되는 순서가 꼬이지 않습니다. 왼쪽 끝은 항상 $i$ 미만이고, 오른쪽 끝은 항상 $i$ 이상입니다. 즉, $\textrm{DP} _{0}, \textrm{DP} _{1}, \cdots, \textrm{DP} _{i-1}$은 $i$번째 인덱스를 보고 있는 시점에 이미 최적해입니다.

짝수 길이 팰린드롬

$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)$로 갱신합시다.

$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)$로 갱신합시다.

예시를 하나 보면 이해에 도움이 될 것 같습니다. $S = \texttt{ABACCA}$일 때, 초기 DP 배열은 $\textrm{DP} = [0, \textrm{INF}, \textrm{INF}, \textrm{INF}, \textrm{INF}, \textrm{INF}, \textrm{INF}]$입니다.

$i = 1$일 때를 봅시다. 구현은 $1$-based index로 짜면 편하고, $S_0 = \varepsilon$임에 유의해주세요.

$$ i=1, j=0: \enspace \underlinesegment{\texttt{A}}\texttt{BACCA} \newline \scriptsize{\textrm{DP} = [0, 1, \textrm{INF}, \textrm{INF}, \textrm{INF}, \textrm{INF}, \textrm{INF}]} $$ $S_1$을 중심으로 하는 다른 팰린드롬이 없으니, $i=2$로 넘어갑시다.

$$ i=2, j=0: \enspace \texttt{A}\underlinesegment{\texttt{B}}\texttt{ACCA} \newline \scriptsize{\textrm{DP} = [0, 1, 2, \textrm{INF}, \textrm{INF}, \textrm{INF}, \textrm{INF}]} $$

우선 $j=0$일 때, $\textrm{DP}_ 2$의 후보는 $\textrm{DP}_ 1 + 1$인 $2$가 될 것입니다.

$$ i=2, j=1: \enspace \underlinesegment{\texttt{ABA}}\texttt{CCA} \newline \scriptsize{\textrm{DP} = [0, 1, 2, 1, \textrm{INF}, \textrm{INF}, \textrm{INF}]} $$

$j$를 하나 더 늘려도 될 것 같습니다. $j=1$일 때, $\textrm{DP} _3$는 $\textrm{DP} _0 + 1 = 1$로 업데이트 됩니다. $i=3$으로 넘어갑시다.

$$ i=3, j=0:\enspace \texttt{AB}\underlinesegment{\texttt{A}}\texttt{CCA} \newline \scriptsize{\textrm{DP} = [0, 1, 2, 1, \textrm{INF}, \textrm{INF}, \textrm{INF}]} $$

$\textrm{DP} _2 + 1 = 3$은 $\textrm{DP} _3 = 1$보다 크므로 최적이 아닙니다. 업데이트 하지 않고 넘어갑니다. 추가로 팰린드롬이 더 없으므로 $i=4$로 넘어갑시다.

$$ i=4, j=0:\enspace \texttt{ABA}\underlinesegment{\texttt{C}}\texttt{CA} \newline \scriptsize{\textrm{DP} = [0, 1, 2, 1, 2, \textrm{INF}, \textrm{INF}]} $$

$\textrm{DP} _4 \leftarrow \textrm{DP} _3 + 1 = 2$로 업데이트 합시다. 이번에는 짝수 길이 팰린드롬을 찾을 수 있습니다.

$$ i=4, j=0:\enspace \texttt{ABA}\underlinesegment{\texttt{CC}}\texttt{A} \newline \scriptsize{\textrm{DP} = [0, 1, 2, 1, 2, 2, \textrm{INF}]} $$

$\textrm{DP} _5 \leftarrow \textrm{DP} _3 + 1 = 2$로 업데이트 합시다. $j$를 하나 더 늘려봅시다.

$$ i=4, j=1:\enspace \texttt{AB}\underlinesegment{\texttt{ACCA}} \newline \scriptsize{\textrm{DP} = [0, 1, 2, 1, 2, 2, 3]} $$

$\textrm{DP} _6 \leftarrow \textrm{DP} _2 + 1 = 3$로 업데이트 합시다.

$i = 5$에서는 길이 $1$짜리 팰린드롬 외에는 찾을 수 없습니다.

$$ i=5, j=0:\enspace \texttt{ABAC}\underlinesegment{\texttt{C}}\texttt{A} \newline \scriptsize{\textrm{DP} = [0, 1, 2, 1, 2, 2, 3]} $$

$\textrm{DP} _5 < \textrm{DP} _4 + 1$이므로 업데이트 하지 않습니다. 마지막으로 $i=6$을 봅시다.

$$ i=6, j=0:\enspace \texttt{ABACC}\underlinesegment{\texttt{A}} \newline \scriptsize{\textrm{DP} = [0, 1, 2, 1, 2, 2, 3]} $$

특이사항으로는, $S_6$을 마지막 조각으로 쪼개도 $3$개로 분할이 가능합니다.

즉, $$ \underlinesegment{\texttt{A}} \underlinesegment{\texttt{B}} \underlinesegment{\texttt{ACCA}} \newline \underlinesegment{\texttt{ABA}} \underlinesegment{\texttt{CC}} \underlinesegment{\texttt{A}} $$ 두 가지 분할 방법이 최적해임을 알 수 있고, $\textrm{DP} _6 = 3$이 잘 정답이 됩니다.

$1$부터 $|S|$까지 순회하며, 각 인덱스마다 투 포인터 느낌으로 최대 $|S|$번 팰린드롬을 찾아나가며 DP 테이블을 갱신하므로, 시간복잡도는 $\mathcal{O}(|S|^2)$가 되고, 공간복잡도는 주어진 문자열과 DP 배열 하나만 있어도 충분하므로 $\mathcal{O}(|S|)$가 됩니다.

코드

#![allow(unused_imports, dead_code)]
use std::{cmp::{max, min, Reverse}, collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}, f64::consts::PI, fmt::{format, Write}, io::{stdin, Read}, mem::swap, str::SplitWhitespace};
 
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;

    for i in 1..=n {
        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 기여창을 보니, 팰린드롬을 전처리한다는 아이디어로 풀었다는 기여가 대부분이었습니다. 궁금해서 구글에 검색해보니 상단에 뜨는 많은 블로그가 그런 풀이로 설명한 것 같은데, 생각보다 더 쉬운 풀이가 있어서 공유하는 차원에서 글을 작성합니다.