[알고리즘 / 백준] 11049 - 행렬 곱셈 순서

www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

 

문제는 위와 같으며 이전에 풀었던 파일 합치기 문제와 유사하게 ABC 행렬의 곱은 (AB)C 또는 A(BC) 중 최소값을 저장하는 방식으로 문제를 해결할 수 있습니다.

 

예제를 살펴보면 먼저 행렬(matrix)을 [[5, 3], [3, 2], [2, 6]] 으로 저장하고 순차적인 행렬의 곱을 나타내는 dp 이차원 배열에 dp[i][i + 1] = matrix[i][0] * matrix[i][1] * matrix[i+1][1] 값을 저장합니다. 

 

그런 다음 먼저 A(BC) 인 경우를 보면 A + BC + A(BC) 값을 구해야 하는데 A(BC) 의 값은 구하고자 행렬의 범위(A~C) 중 가장 앞 행렬(A)의 r 값과 중간 행렬(B)의 r 값 그리고 마지막 행렬(C)의 c 값을 곱해서 구할 수 있다는 것을 알 수 있습니다.

 

그런 다음 (AB)C 인 경우를 보면 AB + C + (AB)C 값을 구해야 하는데 (AB)C  의 값은 구하고자 행렬의 범위(A~C) 중 가장 앞 행렬(A)의 r 값과 중간 행렬(B)의  c 값(= C 행렬의 r 값) 그리고 마지막 행렬(C)의 c 값을 곱해서 구할 수 있다는 것을 알 수 있습니다.

이때는 기존 ABC 에 저장된 값과 계산된 값을 비교하여 더 작은 값을 저장하게 됩니다.

 

파이썬 코드는 다음과 같습니다. Pypy3 로 제출해야 시간 초과 없이 문제를 해결할 수 있습니다.

from sys import stdin

n = int(stdin.readline())
matrix = []  # 주어진 행렬 [[r, c]] 형태로 저장
for _ in range(n):
    matrix.append(list(map(int, stdin.readline().split())))

dp = [[0] * n for _ in range(n)]  # 순차적인 행렬 곱을 표현할 이차원 배열 생성
for i in range(n - 1):
    dp[i][i + 1] = matrix[i][0] * matrix[i][1] * matrix[i + 1][1]


# 3개 이상의 행렬 곱을 구할 모든 경우마다 가장 마지막에 더해질 값 반환
def find_add_num(start, end, mid):
    return matrix[start][0] * matrix[mid][0] * matrix[end][1]


for j in range(2, n):
    i = 0
    while i + j < n:
        for k in range(i, i + j):
            if dp[i][i + j] == 0:
                dp[i][i + j] = dp[i][k] + dp[k + 1][i + j] + find_add_num(i, i + j, k + 1)
            else:
                dp[i][i + j] = min(dp[i][i + j], dp[i][k] + dp[k + 1][i + j] + find_add_num(i, i + j, k + 1))
        i += 1

print(dp[0][n - 1])

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] matrix = new int[n][2];
        for (int i = 0; i < n; i++) {
            matrix[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        int[][] dp = new int[n][n];
        for (int i = 0; i < n - 1; i++) {
            dp[i][i + 1] = matrix[i][0] * matrix[i][1] * matrix[i + 1][1];
        }

        for (int j = 2; j < n; j++) {
            for (int i = 0; i + j < n; i++) {
                for (int k = i; k < i + j; k++) {
                    if (dp[i][i + j] == 0) {
                        dp[i][i + j] = dp[i][k] + dp[k + 1][i + j] + (matrix[i][0] * matrix[k + 1][0] * matrix[i + j][1]);
                    } else {
                        dp[i][i + j] = Math.min(dp[i][i + j], dp[i][k] + dp[k + 1][i + j] + (matrix[i][0] * matrix[k + 1][0] * matrix[i + j][1]));
                    }
                }
            }
        }

        System.out.println(dp[0][n - 1]);
    }
}