[BOJ/Java] 11049. 행렬 곱셈 순서

📌 [BOJ/Java] 11049. 행렬 곱셈 순서

🔗 문제 링크: 백준 11049번 - 행렬 곱셈 순서

---

📖 문제 해석

📌 N개의 행렬이 주어질 때, 모든 행렬을 곱하는 최소 연산 횟수를 구하는 문제이다.
💰 행렬 곱셈 연산 횟수는 A(p×q) × B(q×r) = p × q × r로 계산된다.
🛠️ 행렬을 곱하는 순서에 따라 연산 횟수가 달라지므로 최적의 곱셈 순서를 찾아야 한다.

🎯 핵심 개념

• dp[i][j] = i번째 행렬부터 j번째 행렬까지 곱하는 최소 연산 횟수
• dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost(A[i] ~ A[k], A[k+1] ~ A[j]))
  (i부터 j까지 곱하는 최적의 k를 찾는다.)

---

🛠️ 풀이 과정

1️⃣ 입력 처리 및 초기화

• 행렬 개수 N을 입력받고, 각 행렬의 (행, 열) 크기를 저장한다.
• dp[i][j] 테이블을 생성하고, 대각선(dp[i][i])을 0으로 초기화한다.

2️⃣ DP 테이블 채우기

• 부분 행렬 크기(2개 이상)부터 점진적으로 증가시키며 dp[i][j] 값을 갱신한다.
• dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost) 를 통해 최적의 k를 찾는다.

3️⃣ 최소 연산 횟수 찾기

• dp[1][N]이 전체 행렬을 곱하는 최소 연산 횟수가 된다.

---

💻 코드 구현 (Java)

import java.util.*;

public class Main {
    static int[][] dp;
    static int[][] matrix;
    static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        matrix = new int[N + 1][2]; // 행렬 크기 저장
        dp = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            matrix[i][0] = sc.nextInt(); // 행 크기
            matrix[i][1] = sc.nextInt(); // 열 크기
        }

        System.out.println(matrixChainOrder());
    }

    public static int matrixChainOrder() {
        for (int len = 2; len <= N; len++) { // 부분 행렬 길이 (2개 이상)
            for (int i = 1; i + len - 1 <= N; i++) { // 시작 인덱스
                int j = i + len - 1; // 끝 인덱스
                dp[i][j] = Integer.MAX_VALUE;

                for (int k = i; k < j; k++) { // 중간 지점 k
                    int cost = dp[i][k] + dp[k + 1][j] + (matrix[i][0] * matrix[k][1] * matrix[j][1]);
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }

        return dp[1][N]; // 전체 행렬을 곱하는 최소 연산 횟수
    }
}

---

⏱️ 시간 복잡도 분석

📌 O(N³) (최대 500³ = 약 1억 2500만 연산)
💡 dp[i][j]를 구하기 위해 중간 지점 k를 탐색해야 하므로 **O(N²) × O(N) = O(N³)**의 시간 복잡도를 가진다.
🔥 다행히 N ≤ 500이므로 DP를 사용하여 충분히 해결 가능하다.

---

💡 느낀점

✅ 최적의 행렬 곱셈 순서를 찾는 DP 문제로,
단순히 차례로 곱하는 것이 아닌 부분 문제를 정의하고 최적의 순서를 찾는 것이 중요했다.

✅ 행렬 곱셈 연산 횟수를 구할 때, 행렬 크기를 고려하는 것이 핵심이었다.

✅ 파일 합치기(11066) 문제와 유사한 방식으로 해결할 수 있었다! 🚀