백준 11049 : 행렬 곱셈 순서 - javascript(dp)

문제 출처 

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

 

정답 풀이 

"행렬 곱셈 순서"는 dp를 이용해 푸는 전형적인 문제다. 

최소 연산 횟수를 구하는 문제 

 

행렬곱셈은 결합법칙을 따르기 때문에, 곱하는 순서에 따라 연산 횟수가 달라짐 

 

문제 해결 전략

 

1. 행렬 곱셈 연산의 특징:  두 행렬 A (r1 x c1)와 B (r2 x c2)를 곱하면 새로운 행렬은 (r1 x c2)가 되고, 연산 횟수는 r1 * c1 * c2가 됩니다. 연산 순서를 바꾸면 그에 따라 필요한 곱셈 횟수가 달라집니다.

 

2. dp: DP 테이블을 사용하여 행렬을 곱하는 순서별 최소 연산 횟수를 저장합니다. dp[i][j]는 i번째 행렬부터 j번째 행렬까지 곱하는 데 필요한 최소 연산 횟수를 나타냅니다.

정답 코드 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const n = parseInt(input[0]);
const matrices = input.slice(1).map(line => line.split(' ').map(Number));

const dp = Array.from({ length: n }, () => Array(n).fill(Infinity));
const dimensions = matrices.map(([r, c]) => [r, c]);

for (let i = 0; i < n; i++) {
    dp[i][i] = 0;  // 한 개의 행렬은 곱셈 연산이 필요하지 않음
}

for (let length = 1; length < n; length++) {
    for (let i = 0; i + length < n; i++) {
        const j = i + length;
        for (let k = i; k < j; k++) {
            const cost = dp[i][k] + dp[k + 1][j] + dimensions[i][0] * dimensions[k][1] * dimensions[j][1];
            dp[i][j] = Math.min(dp[i][j], cost);
        }
    }
}

console.log(dp[0][n - 1]);

 

의사 코드 추가 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n'); 
// 입력을 읽어온 후 처리 (첫 번째 줄은 행렬 개수, 나머지는 행렬의 크기 정보)
const n = parseInt(input[0]);  // 행렬의 개수
const matrices = input.slice(1).map(line => line.split(' ').map(Number)); 
// 각 행렬의 크기를 배열로 저장

const dp = Array.from({ length: n }, () => Array(n).fill(Infinity));  
// DP 테이블을 생성하고, 최소값을 찾기 위해 초기값을 Infinity로 설정

// 행렬의 차원 정보를 저장 (행, 열)
const dimensions = matrices.map(([r, c]) => [r, c]);

// DP의 대각선은 0으로 초기화 (한 개의 행렬은 곱셈이 필요하지 않기 때문)
for (let i = 0; i < n; i++) {
    dp[i][i] = 0;
}

// 연속된 행렬을 처리하는 범위를 length로 설정 (1개부터 n개까지)
for (let length = 1; length < n; length++) {
    for (let i = 0; i + length < n; i++) {
        const j = i + length;
        // i부터 j까지의 행렬 곱셈을 처리
        for (let k = i; k < j; k++) {
            const cost = dp[i][k] + dp[k + 1][j] + dimensions[i][0] * dimensions[k][1] * dimensions[j][1];
            // i에서 j까지 행렬 곱셈에 필요한 최소 비용 계산
            dp[i][j] = Math.min(dp[i][j], cost); 
            // 더 작은 연산 횟수가 있으면 갱신
        }
    }
}

// 최종 결과 출력 (dp[0][n-1]이 최소 연산 횟수)
console.log(dp[0][n - 1]);