[Javascript] 프로그래머스 - 최적의 행렬 곱셈

문제 설명

여러 개의 행렬을 곱할 때, 곱셈의 순서에 따라 연산 횟수가 달라질 수 있습니다.
주어진 행렬들의 크기를 이용하여 곱셈 연산 횟수가 최소가 되도록 곱하는 경우의 연산 횟수를 구하는 문제입니다.

---

제한 사항

• 행렬의 개수는 3 이상 200 이하입니다.
• 각 행렬의 행과 열 크기는 200 이하입니다.
• 계산할 수 없는 행렬이 입력으로 주어지는 경우는 없습니다.

---

해결 방법

알고리즘: 동적 계획법 (Dynamic Programming)

• dp[i][j]: i번째 행렬부터 j번째 행렬까지 곱할 때 최소 연산 횟수를 저장하는 배열을 사용합니다.
• dp[i][i] = 0: 자기 자신만 있는 경우 연산이 필요 없으므로 0으로 초기화합니다.
• dp[i][j]를 계산할 때, 가능한 모든 k에 대해 분할하여 최소 비용을 구합니다.
  • dp[i][j] = min(dp[i][k] + dp[k+1][j] + matrices[i] * matrices[k+1] * matrices[j+1])
  • matrices[i], matrices[k+1], matrices[j+1]는 곱할 행렬의 크기를 고려한 곱셈 연산 횟수입니다.

---

시간 복잡도

• 3중 반복문(O(N³))을 사용하므로, 최대 200³ = 8,000,000 연산으로 충분히 해결할 수 있습니다.

---

구현 코드

function solution(matrix_sizes) {
  const n = matrix_sizes.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(Infinity));
  const matrices = [matrix_sizes[0][0]];

  for (let i = 0; i < n; ++i) {
    matrices.push(matrix_sizes[i][1]);
    dp[i][i] = 0;
  }

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;

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

  return dp[0][n - 1];
}