썸네일 출처: https://ye-yo.github.io/thumbnail-maker/

---

📖 문제

11066번: 파일 합치기

주어진 파일들을 하나로 합치는 최소 비용을 구하는 문제이다.
동적계획법을 잘 활용하면 풀 수 있다.

---

💡 아이디어

1. 동적계획법 상태 정하기

파일을 합치는 작업은 연속된 두 개의 파일 혹은 임시파일을 하나로 합치는 기본 작업 여러개로 이루어져 있다. 이 말인 즉, 모든 상태는 그 이전 상태 두 개의 합으로 표현할 수 있다는 것이다.

문제에 나온 C1, C2, C3, C4예제를 보자. (Cx, Cy)를 Cx에서 Cy까지 파일을 합치는 최소비용이라고 하면 최종적으로 구해야 하는 (C1, C4)는 (C1) + (C2, C4) or (C1, C2) + (C3, C4) or (C1, C3) + (C4) 세 가지 중 가장 비용이 낮은 값이다.

그림에서 보이듯 구해야 하는 범위를 보다 크기가 작은 두 두분의 합으로 표현할 수 있다.
합치는 파일의 수와 시작지점을 상태의 기준으로 두면 위 그림에서 노란 사각형과 빨간 사각형에 해당하는 상태를 모두 표현할 수 있다.

총 파일의 개수가 k일때 i번째 파일부터 i+L번째 파일까지를 합치는 최솟값을 dp[L][i]라고 두고, L=1부터 L=k-1까지 부분계산값을 구해나가면 dp[k-1][0]이 우리가 찾는 답이 될 것이다.

2. 부분계산식 찾아내기

한 상태를 그보다 작은 두 부분의 합으로 표현할 때, 그 계산식은 다음과 같이 표현할 수 있다.

비용의 합 =
오른쪽 부분을 만드는데 드는 최소 비용 + 왼쪽 부분을 만드는데 드는 최소 비용
+ 각 부분의 파일 길이의 합

dp[3][0]을 예로 들면 dp[3][0] = dp[1][0] + dp[0][2] + (각 부분의 크기)이다. 양쪽 부분의 최소 비용은 dp에 저장되므로 괜찮지만, 각 부분의 크기는 dp에 표현할 수 없으므로 따로 배열을 만들어 저장했다.

i번째 파일부터 i+L번째 파일까지를 합친 파일의 크기를 c[L][i]라고 정의했다.

그림에서처럼 L=0일 때는 각 인덱스의 파일의 크기가 저장되고, L>=1부터는 c[L][i] = c[L-1][i] + c[0][i+L]이므로 L=1일 때 부터 하나씩 구해 나가면 테이블을 다 채울 수 있다.

이제 필요한 것은 dp[L][i]의 값이 될 수 있는 후보를 어떻게 탐색하느냐인데, 우선 그림을 보자.

그림에서 보듯 첫 부분의 L이 0일때, 1일때, 2일때에 따라 각각 파란색, 초록색, 노란색 영역이 계산값에 포함된다.
따라서 첫 부분의 L값을 x라고 두면 다음과 같은 일반식이 나온다.

dp[L][i] = MIN(dp[x][i] + dp[L-x-1][i+x+1] + c[x][i] + c[L-x-1][i+x+1])
(x = 0..l-1)

이제 이 식을 통해 dp테이블을 채우고, dp[k-1][0]값을 출력하면 된다.

---

⏱️ 최적화

K의 범위가 3~500으로 정해져 있기 때문에 벡터 대신 배열을 사용하면 속도가 향상된다.

테스트케이스가 여러개이기 때문에 출력에 버퍼를 사용하는 것이 좋다. 하지만 BufWriter 와writeln! 매크로를 사용하여 직접 StdOut에 출력하는 대신에, 버퍼 스트링을 하나 만들어서 모든 출력값을 스트링에 쓴 후 스트링을 한번에 출력하는 방식을 사용했다. 이 방식은 메모리를 조금 더 잡아먹지만, 출력 속도는 전자에 비해 빠르다.

	// Using BufWriter to StdOut
    let stdout = stdout();
    let mut writer = BufWriter::new(stdout);
    for _ in 0..n {
    	...
        writeln!(writer, "{}", dp[k-1][0]).unwrap();
    }
    
	// Using String buffer
	let mut output = String::new();
    for _ in 0..n {
    	...
        writeln!(output, "{}", dp[k-1][0]).unwrap();
    }
    println!("{output}");

---

✏️ 코드

use std::cmp::{max, min, Ordering};
use std::io::{stdin, Read, Write, stdout, BufWriter};
use std::fmt::Write as fWrite;

const K_MAX: usize = 500;

fn main() {
    let mut input = String::new();
    stdin().read_to_string(&mut input).unwrap();
    let mut input = input.split_ascii_whitespace().flat_map(str::parse::<usize>);
    let n = input.next().unwrap();

    let mut output = String::new();

    let mut file_sizes = [[0usize; K_MAX]; K_MAX];
    let mut dp = [[0usize; K_MAX]; K_MAX];
    for _ in 0..n {
        let k = input.next().unwrap();
        for i in 0..k {
            file_sizes[0][i] = input.next().unwrap();
        }
        for l in 1..k {
            for i in 0..k-l {
                file_sizes[l][i] = file_sizes[l-1][i] + file_sizes[0][i+l];
            }
        }
        for l in 1..k {
            for i in 0..k-l {
                let mut min_cost = usize::MAX;
                for x in 0..l {
                    min_cost = min(min_cost, dp[x][i] + dp[l - x - 1][i + x + 1] 
                    + file_sizes[x][i] + file_sizes[l - x - 1][i + x + 1]);
                }
                dp[l][i] = min_cost;
            }
        }
        writeln!(output, "{}", dp[k-1][0]).unwrap();
    }
    println!("{output}");
}