단계적으로 최소비용을 구해나간다는 문제의 서술로부터 다이나믹 프로그래밍을 떠올릴 수 있었습니다.
$C(i, j)$를 인덱스 $i$부터 $j$까지 파일을 합하는 최소 비용이라 정의하면,
$$C(i, j) = \min_{i \le k \lt j}[C(i, k) + C(k + 1, j)] + \sum_{n = i}^{j} \mathrm{Size}[n]$$
$\mathrm{Size}[i..j]$는 부분합을 이용해 $O(1)$만에 구할 수 있으므로 전체 시간복잡도는 $O(K^3)$이 됩니다.
코드
use std::fmt::Write;
use std::io::{stdin, Read};
fn main() {
let mut input = String::new();
stdin().read_to_string(&mut input).unwrap();
let mut output = String::new();
let mut input = input.split_ascii_whitespace().map(str::parse).flatten();
let t = input.next().unwrap();
for _ in 0..t {
let k = input.next().unwrap();
let mut sum = vec![0];
sum.extend(input.by_ref().take(k).scan(0, |state, x| {
*state += x;
Some(*state)
}));
let mut min_cost = Matrix(vec![0; k * k], k);
for gap in 1..k {
for i in 0..k - gap {
let mut min = usize::MAX;
for j in i..i + gap {
min = min.min(min_cost[i][j] + min_cost[j + 1][i + gap]);
}
min_cost[i][i + gap] = min + sum[i + gap + 1] - sum[i];
}
}
writeln!(output, "{}", min_cost[0][k - 1]).ok();
}
print!("{}", output);
}
struct Matrix<T>(Vec<T>, usize);
impl<T> std::ops::Index<usize> for Matrix<T> {
type Output = [T];
fn index(&self, index: usize) -> &Self::Output {
&self.0[index * self.1..][..self.1]
}
}
impl<T> std::ops::IndexMut<usize> for Matrix<T> {
fn index_mut(&mut self, index: usize) -> &mut Self::Output {
&mut self.0[index * self.1..][..self.1]
}
}