백준 11066: 파일 합치기 - javascript(dp)

문제 출처 

https://www.acmicpc.net/problem/11066

 

정답 코드 

전략

1. 주어진 파일을 순서대로 합치고, 파일을 합치는 비용은 두 파일 크기의 합이다. 

2. 여러 파일을 합치기 위해 최적 부분 구조를 활용한 dp를 사용하여, 부분 문제들의 최솟값을 저장하며 문제를 해결한다. 

3. 합칠 파일의 범위를 설정하고, 그 범위 내에서 파일을 합치는 최소 비용을 찾는 방식으로 접근한다. 

 

해결 과정

1. 먼저 각 파일의 크기를 저장하고, 파일의 누적합 배열을 미리 구한다. 

2. dp 테이블을 설정하여 각 구간에서의 최소 비용을 기록한다. 

3. 주어진 파일들을 두 그룹으로 나누고, 각 그룹을 합친 뒤 다시 합치는 비용을 반복적으로 계산한다. 

 

누적합 배열 

: 0번째 부터 i 번째 파일까지의 크기 합을 저장하며, 이를 통해 특정 구간의 파일 크기 합을 빠르게 구현할 수 있다. 

 

dp 테이블 

: dp[start][end]는 start에서 end 까지 파일을 합치는데 드는 최소 비용을 저장한다. 

 

구간 나누기 

: 파일을 두 두간으로 나누고, 각 구간의 최소 비용을 계산한 뒤 합친 비용을 더해 구간 전체의 최소 비용을 구한다. 

 

결과 출력 

: dp 테이블에서 최종적으로 0번 파일부터 n-1번 파일까지 합친 최소 비용을 반환한다. 

정답 풀이 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const tc = Number(input.shift());

for (let i = 0; i < tc * 2; i += 2) {
    let n = Number(input[i]);
    let file = input[i + 1].split(' ').map(v => +v);
    console.log(solution(n, file));
}

function solution(n, file) {
    // DP 테이블과 누적합 배열 선언
    const dp = Array.from({ length: n }, () => Array(n).fill(0));
    const sum = Array(n).fill(0);

    // 누적합 구하기
    sum[0] = file[0];
    for (let i = 1; i < n; i++) {
        sum[i] = sum[i - 1] + file[i];
    }

    // DP로 최소 비용 구하기
    for (let size = 1; size < n; size++) {  // size: 파일을 합치는 구간의 크기
        for (let start = 0; start + size < n; start++) {  // start: 시작 파일의 인덱스
            const end = start + size;
            dp[start][end] = Infinity;

            // 중간 지점을 기준으로 두 그룹으로 나누어 최소 비용을 계산
            for (let mid = start; mid < end; mid++) {
                const cost = dp[start][mid] + dp[mid + 1][end] + (sum[end] - (start > 0 ? sum[start - 1] : 0));
                dp[start][end] = Math.min(dp[start][end], cost);
            }
        }
    }

    return dp[0][n - 1];  // 0번부터 n-1번까지 합치는 최소 비용 반환
}