[KOITP]Matrix Chain Multiplication

출처 : http://www.koitp.org/problem/MATRIX_CHAIN_MULTIPLICATION/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	278	106 (38%)	95

문제

$M\times N$ 크기의 행렬 $A$와 $N\times K$ 크기의 행렬 $B$의 행렬 곱셈 $AB$를 생각해보자. 두 행렬의 곱셈 과정의 연산 횟수는 $MNK$ 이다. 행렬 곱셈에는 교환 법칙 $AB=BA$는 성립하지 않지만, 결합 법칙 $\left(AB\right)C=A\left(BC\right)$는 성립한다. 결합 법칙에 의해 어떤 순서로 곱셈을 하는지에 따라 전체 연산 횟수가 차이난다.

예를 들어, 세 행렬 $A_1,A_2,A_3$가 있다고 하자. $A_1$은 $10\times 100$ 크기, $A_2$는 $100\times 5$ 크기, $A_3$은 $5\times 50$ 크기의 행렬이다. $\left(A_1{A}_2\right)A_3$ 순서로 곱셈을 할 경우, 전체$10\times 100\times 5+10\times 5\times 50=7,500$번의 연산이 필요하고, $A_1\left(A_2{A}_3\right)$ 순서로 곱셈할 경우, 전체 $100\times 5\times 50+10\times 100\times 50=75,000$번의 연산이 필요하다.

$n$개의 행렬 $A_1,A_2,A_3,\dots ,A_n$이 있다. 행렬 $A_i$의 크기는 $a_i\times a_{i+1}$이다. 이 때, $A_1{A}_2{A}_3\dots A_n$을 계산하는데 필요한 연산의 최소 횟수를 구하는 프로그램을 작성하라.

입력

첫 줄에 행렬의 개수 $n$이 주어진다. ($2\le n\le 500$)

둘째 줄에 행렬의 크기를 나타내는 자연수 $n+1$개가 공백으로 구분되어 주어진다. $i$번째로 주어지는 수는 $a_i$이다. ($a_i\le 100$)

출력

첫 줄에 $A_1{A}_2{A}_3\dots A_n$를 구하기 위해 필요한 연산의 최소 횟수를 출력한다.

힌트

예제 입력

3
10 100 5 50

예제 출력

7500

< Comment >

 문제를 풀다가 몸이 조금 안 좋아, 평소보다는 빨리 포기하고 힌트를 보고 풀었습니다ㅠㅠ

 다른 것보다도 결국 DP에서는 아이디어가 중요한 것 같은데, 이전에 유사한 문제를 풀어봤음에도 불구하고 제대로 떠올리지 못했었습니다. 우선 여기서 행렬곱의 횟수는 3개의 연속된 숫자를 곱한 값인데, 이를 DP로 아래와 같이 정의됩니다.

D(i, j) : i부터 j번째까지의 행렬을 곱하는 데 필요한 최소의 횟수
D(i, j) = D(i, k) + D(k+1, j) + (A[i] * A[k+1] * A[j])

 점화식으로 세워둔 것과 내용이 조금 달라서 헷갈리실 수도 있는데, 점화식에서의 k는 i와 j사이에 있는 임의의 숫자입니다. 그래서 실제로 구현을 할 때에는, i+k와 같이 구현해 두었을 뿐입니다. 조금 더 생각해봤다면 풀었을 수도 있었을텐데 조금 아쉽습니다.

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

public class MatrixManipulation {

    public static int N = 0;
    public static int matrixs[] = null;
    public static int cache[][] = null;

    public static void main (String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        matrixs = new int[N + 2];
        cache = new int[N+1][N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N+2 ; i++){
            matrixs[i] = Integer.parseInt(st.nextToken());
        }

        int result = dp(1, N);
        System.out.println(result);
    }

    // i번째부터 j번째까지 행렬의 곱연산 최소 수를 리턴
    public static int dp (int i, int j) {

        if (i == j-1) {
            return matrixs[i] * matrixs[i+1] * matrixs[i+2];
        } else {
            if (i >= j){
                return 0;
            }
            if(cache[i][j] != 0) {
                return cache[i][j];
            }
        }

        int ret = Integer.MAX_VALUE;
        for (int k = 0 ; k < j-i ; k++) {
            ret = Math.min(ret, dp(i, i+k) + dp(i+k+1, j) + (matrixs[i] * matrixs[i+k+1] * matrixs[j+1]));
        }

        return cache[i][j] = ret;
    }
}