[백준] BOJ_11049 행렬 곱셈 순서

1. 문제 정보

• 문제 요약: 크기가 인 행렬 와 인 행렬 를 곱할 때 필요한 스칼라 곱셈 연산 횟수는 입니다. 주어진 개의 행렬을 모두 곱할 때, 연산 횟수의 최솟값을 구하는 문제입니다. 행렬의 곱셈 순서에 따라 연산 비용이 천차만별로 달라질 수 있습니다.
• 난이도: Gold III
• 링크: https://www.acmicpc.net/problem/11049

---

2. 접근 방식

이 문제는 그리디(Greedy) 알고리즘으로 풀 수 없습니다. 당장 눈앞에 보이는 적은 비용의 곱셈을 먼저 수행한다고 해서 전체 비용이 최소가 된다는 보장이 없기 때문입니다. 전체 문제를 작은 부분 문제로 쪼개고, 그 결과를 저장해 사용하는 DP(Dynamic Programming) 접근이 필요합니다.

2-1. 문제의 본질

행렬 $A, B, C, D$ 4개를 곱한다고 가정해 봅시다 ($A \times B \times C \times D$).이 행렬 전체를 곱하는 마지막 단계는 반드시 어떤 두 개의 덩어리(부분 결과)의 곱으로 표현됩니다.예를 들어, 마지막 연산은 다음 중 하나일 것입니다.

1.$(A) \times (BCD)$
2.$(AB) \times (CD)$
3.$(ABC) \times (D)$

즉, 전체 범위 $(i \dots j)$의 최소 비용을 구하기 위해서는, 그 사이의 어떤 지점 를 기준으로 두 부분으로 쪼갰을 때의 최솟값을 찾아야 합니다. 이것이 바로 최적 부분 구조입니다.

2-2. 알고리즘 설계

이 문제는 전형적인 구간 DP(Interval DP) 유형입니다.

일반적인 선형 DP가 dp[1]부터 dp[N]까지 순차적으로 채워진다면, 구간 DP는 구간의 길이(Length)를 늘려가며 테이블을 채워야 합니다.

1. 길이(len) 2: 인접한 두 행렬의 곱셈 비용을 구합니다. ($AB, BC, CD \dots$)
2. 길이(len) 3: 세 행렬의 곱셈 비용을 구합니다. ($ABC, BCD \dots$)
   이때, 앞서 구한 길이 2의 결과값을 재사용합니다.
3. $\dots$
4. 길이(len) N: 전체 행렬의 곱셈 비용을 구합니다.

2-3. 점화식 / 수식

우리가 구할 $DP[i][j]$의 정의는 다음과 같습니다.

$DP[i][j]$ : $i$번 행렬부터 $j$번 행렬까지 곱했을 때의 최소 연산 횟수

이를 구하기 위해 $i$와 $j$ 사이의 분기점 $k$ ($i \le k < j$)를 순회하며 최솟값을 찾습니다.

$DP[i][j] = \min_{i \le k < j} (DP[i][k] + DP[k+1][j] + Cost(i, k, j))$

여기서 $Cost(i, k, j)$는 만들어진 두 행렬 덩어리를 합치는 비용입니다.

• 앞 덩어리 $(i \dots k)$의 결과 행렬 크기: $Row_i \times Col_k$
• 뒤 덩어리 $(k+1 \dots j)$의 결과 행렬 크기: $Row_{k+1} \times Col_j$
• 행렬 곱셈이 가능하려면 $Col_k == Row_{k+1}$이어야 하므로, 합치는 비용은 $Row_i \times Col_k \times Col_j$가 됩니다.

따라서 최종 점화식은 다음과 같습니다.

$DP[i][j] = \min (DP[i][k] + DP[k+1][j] + (arr[i][0] \times arr[k][1] \times arr[j][1]))$

---

3. 코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
    // 최솟값 비교를 위한 초기화 값. 오버플로우가 나지 않는 선에서 충분히 큰 값이어야 합니다.
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][2];
        
        // 행렬의 크기 정보 입력 (r, c)
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            arr[i][0] = y;
            arr[i][1] = x;
        }

        // dp[i][j]: i번째 행렬부터 j번째 행렬까지의 최소 곱셈 비용
        int[][] dp = new int[N][N];

        // len: 곱하는 행렬의 개수 (구간의 길이)
        // 2개부터 시작하여 N개까지 늘려감
        for (int len = 2; len <= N; len++) {
            // i: 구간의 시작점
            for (int i = 0; i <= N - len; i++) {
                // j: 구간의 끝점
                int j = i + len - 1;
                dp[i][j] = INF;

                // k: 구간을 나누는 분기점 (i <= k < j)
                for (int k = i; k < j; k++) {
                    // 점화식 적용: 앞부분 비용 + 뒷부분 비용 + 두 덩어리를 합치는 비용
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + (arr[i][0] * arr[k][1] * arr[j][1]));
                }
            }
        }
        
        // 0번부터 N-1번(전체)까지 곱했을 때의 최소 비용 출력
        System.out.println(dp[0][N - 1]);
    }
}

---

4. 회고 및 배운 점

시간 복잡도 분석: $O(N^3)$의 정당성

이 코드는 3중 반복문(len, i, k)으로 구성되어 있습니다.

• len: $2 \dots N$
• i: $0 \dots N-len$
• k: $i \dots j-1$

전체 연산 횟수는 대략 $\sum_{len=2}^{N} (N-len+1) \times (len-1) \approx \frac{N^3}{6}$ 정도가 됩니다.

문제 조건에서 $N \le 500$이므로, $500^3 = 125,000,000$ (1.25억)입니다. Java 11 기준으로 1초라는 시간 제한은 다소 빠듯할 수 있으나, 단순 연산(덧셈, 곱셈, 비교) 위주이므로 통과 가능한 복잡도입니다. 만약 $N$이 1,000 이상이었다면 이 $O(N^3)$ 알고리즘으로는 해결할 수 없었을 것입니다.

구현 디테일

• DP 초기화: dp[i][j]를 갱신할 때 Math.min을 사용하므로, 초기값을 Integer.MAX_VALUE로 설정해야 합니다. 만약 0으로 초기화된 상태에서 비교했다면 최솟값 갱신이 이루어지지 않았을 것입니다.
• 인덱스 관리: 행렬 곱셈 문제에서 가장 헷갈리는 부분은 과 를 곱할 때 비용 계산식입니다. 코드에서 arr[i][0](시작 행렬의 행), arr[k][1](중간 행렬의 열 = 분기점), arr[j][1](끝 행렬의 열)을 정확하게 매핑한 점이 정답의 핵심이었습니다.