[백준 11049번] 행렬 곱셈 순서

문제 링크: 11049번 행렬 곱셈 순서

https://www.acmicpc.net/problem/11049

 

아이디어는 다음의 두 지점에서 얻었다.

• 2차원 배열을 통해 부분 문제의 해를 저장해둘 수 있다. (원래 알고 있던 접근법)
• 행렬의 계산 순서는 바꿀 수 없다. (문제에서 제시된 조건)

계산 순서를 바꿀 수 없다는 조건은 대수롭지 않은 것으로 넘길 수 있지만, 굉장히 많은 경우의 수를 줄여주는 중요한 조건이다. 이는 바로 뒤 문제인 파일 합치기(문제 링크, 포스트 링크)에서도 마찬가지다.

여러가지 방법으로 저장할 수 있겠지만, 나는 dp[i][j]에서 i는 부분행렬의 마지막 행렬을, j는 부분행렬의 길이를 나타낼 때, dp[i][j]는 matrix[i-j+1:i+1]까지의 최소 연산 횟수를 나타내는 것으로 상정했다.

 

i   ＼   j	1	2	3	4	5
1 (A)	A
2 (B)	B	AB
3 (C)	C	BC	ABC
4 (D)	D	CD	BCD	ABCD
5 (E)	E	DE	CDE	BCDE	ABCDE

 

처음에는 Matrix 클래스를 선언하여 각 인스턴스가 행의 수, 열의 수, 최소 연산 횟수를 담고 있도록 했으나 이를 개선한 결과 테스트 결과 상으로 시간은 7배, 메모리는 10배 정도 덜 사용한 것으로 보이기에 최적화는 굉장히 중요한 요소라고 할 수 있겠다. 처음에 클래스를 선언하였던 이유는 최소 연산 횟수 이외에 행의 수와 열의 수를 알고 있어야 두 행렬을 곱할 때 추가되는 새로운 연산 횟수를 구할 수 있다고 생각했기 때문이다. 하지만 dp[i1][j1]과 dp[i2][j2]를 이용해 두 행렬을 곱할 때에는 i1, i2, i3, i4만 가지고도 새로운 연산 횟수를 구할 수 있다.

 

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

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

    public static int cal(int i1, int j1, int i2, int j2) {
        return matrix[i1-j1+1][0] * matrix[i1][1] * matrix[i2][1] + dp[i1][j1] + dp[i2][j2];
    }

    public static void main(String[] args) throws IOException {
        /* input */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        /* create matrix */
        matrix = new int[n+1][2];
        for (int i = 1; i <= n; i++) {
            String[] s = br.readLine().split(" ");
            matrix[i][0] = Integer.parseInt(s[0]);
            matrix[i][1] = Integer.parseInt(s[1]);
        }

        /* create dp */
        dp = new int[n+1][n+1];
        for (int i = 1; i <= n; i++)
            dp[i][1] = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= i; j++) {
                int min = Integer.MAX_VALUE;
                for (int t = 1; t <= j-1; t++) {
                    int cur = cal(i - j + t, t, i, j - t);
                    if (cur < min)
                        min = cur;
                }
                dp[i][j] = min;
            }
        }

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