[백준 / BOJ] 11049 행렬 곱셈 순서

문제

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

11049번: 행렬 곱셈 순서

N개의 행렬이 주어진다.

행렬 A의 크기를 N*M, 행렬 B의 크기를 M*K라고 할때,

각 행렬을 곱할때 필요한 곱셈 연산 수는 N*M*K이다.

모든 행렬을 곱하는데 필요한 최소 연산횟수를 구하는 문제다.

---

풀이

다이나믹 프로그래밍으로 풀리는 문제다.

처음엔 그리디로 생각했지만, 현재 최적값이 나중에도 최적이라는 보장이없기때문에 그리디로는 풀기 힘들어보인다.

 

이 문제처럼 dp식이 한번에 떠오르지 않거나, 헷갈린다면, 모든 경우를 나열해보면 도움이 된다.

배열이 5개있고, 각 배열에 1번부터 5번까지 마크가 되어있다고 하자.

각 배열을 곱하는 순서는 다음과 같이 나올수있다.

 

((((12)3)4)5)
(((12)3)(45))
.

.

.

(1(2(3(45))))
(12)(3(45))
((1(23))(45))

 

중복되는 부분이 보이므로 최적화를 시켜줄수있다.

나올수있는 모든 경우가 최대 N^2이므로, 중복되는 부분을 최적화시켜주면, 약 O(N^2)의 시간복잡도로 해결이 가능한 문제였다.

 

dp코드

    private Array getDp(int left, int right){
        if(dp[left][right] != null) return dp[left][right];
        if(left - right == 1 || left - right == -1) 
            return dp[left][right] = calcArray(arr[left], arr[right]);
        Array ansArray = new Array(INF, INF, INF);
        for(int i = 1; i < right-left; i++) 
            ansArray = getMin(ansArray, getMin(
                calcArray(dp[left][left+(i-1)], getDp(left+i, right)),
                calcArray(getDp(left, right-i),dp[right-(i-1)][right])
                ));
        return dp[left][right] = ansArray;
    }

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/11049%20%ED%96%89%EB%A0%AC%20%EA%B3%B1%EC%85%88%20%EC%88%9C%EC%84%9C/Main.java

devxb/JJUNalgo