[BOJ] 11049: 행렬 곱셈 순서

문제

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

입력

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

풀이

두 행렬의 곱의 수는

좌항의 행의 수 * 좌항의 열의 수(우항의 행의 수와 같음) * 우항의 열의 수이다.

 

이때 이 문제는 다수의 행렬 연산을 최적의 횟수로 구해야 하기 때문에 DP를 이용해서 풀이했다.

 

2차원의 dp 배열은 1차 인덱스 부터 2차 인덱스의 행렬 곱셈 연산의 최적의 값을 저장한다.

즉, [[5, 3], [3, 2], [2, 6]] 이렇게 3개의 행렬이 있을 때,

 

dp[1][1]는 1번 부터 1번 행렬의 행렬 곱을 구하는 최소 연산 횟수로 [5, 3]의 최적 행렬 곱 횟수임으로 이 값은 0이고,

dp[1][2]는 1번 부터 2번 행렬의 행렬 곱을 구하는 최소 연산 횟수로 [5, 3], [3, 2] 두 행렬의 최적 행렬 곱 횟수임으로 이 값은 30 이며,

dp[2][3]은 2번 부터 3번 행렬의 행렬 곱을 구하는 최소 연산 횟수로 [3, 2], [2, 6] 두 행렬의 최적 행렬 곱 횟수음으로 이 값은 36 이다.

 

그렇기 때문에 이 문제의 목표는 dp[1][N]을 구하는 것이다.

 

이 문제에서 1차 인덱스와 2차 인덱스가 같거나, (2차 인덱스 = 1차 인덱스 + 1) 과 같은 상황은 분명한 값이기 때문에 초기화 해주면 된다.

그 이후의 연산이 문제인데

이를 문제의 예시로 들어 dp[1][3]을 풀이하는 과정으로 설명하자면 dp[1][3]은

A 행렬과 B 행렬을 먼저 계산하고 C를 계산하는 (AB)C의 방법과,
B 행렬과 C 행렬을 먼저 계산하고 A를 계산하는 A(BC)의 방법이 있다.

 

(AB)C의 방법

dp[1][2] + dp[3][3] + {(AB의 행의 수) * (AB의 열의 수) * (C의 열의 수)}

 

A(BC)의 방법

 

dp[1][1] + dp[2][3] + {(A의 행의 수) * (A의 열의 수) * ((BC의 열의 수)}

이런 식으로 연산할 수 있고, 이를 일반화시켜 계산해나가면 dp[1][N]을 구할 수 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Matrix[] matrices = new Matrix[N + 1];
        int[][] dp = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            matrices[i] = new Matrix(r, c);
        }

        for (int i = 1; i < N; i++) {
            dp[i][i + 1] = matrices[i].r * matrices[i].c * matrices[i + 1].c;
        }

        for (int i = 3; i <= N; i++) {
            for (int left = i; left <= N; left++) {
                int right = left - i + 1;
                int section = i - 1;
                int optimized = Integer.MAX_VALUE;


                for (int k = 0; k < section; k++) {
                    int rightStart = right;
                    int rightEnd = right + k;
                    int leftStart = rightEnd + 1;
                    int leftEnd = left;
                    Matrix rightMatrix = getMutipliedMatrix(matrices, rightStart, rightEnd);
                    Matrix leftMatrix = getMutipliedMatrix(matrices, leftStart, leftEnd);
                    optimized = Math.min(
                            optimized,
                            dp[rightStart][rightEnd] + dp[leftStart][leftEnd] +
                                    rightMatrix.r * rightMatrix.c * leftMatrix.c
                    );
                }
                dp[right][left] = optimized;
            }
        }

        System.out.println(dp[1][N]);
    }

    public static Matrix getMutipliedMatrix(Matrix[] matrices, int right, int left){
        return new Matrix(matrices[right].r, matrices[left].c);
    }

    static class Matrix{
        int r;
        int c;

        public Matrix(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}