dp로 풀어야 하는 문제다.
[[5, 3], [3, 10], [10, 6]]의 경우 앞 부터 행렬을 ABC라고 표기하겠다.
만약 AB를 먼저 곱한 뒤 C를 곱하면 총 연산 횟수가 5 x 3 x 10 + 5 x 10 x 6 = 450
A를 곱하기 전에 BC를 먼저 곱하면 총 연산 횟수가 3 x 10 x 6 + 5 x 3 x 6 = 270이 된다.
즉, 행렬을 곱하는 순서에 따라서 연산 횟수가 달라지는 것이고, 문제에선 최소 연산 횟수를 반환해주면 된다.
이를 구하기 위해 DP를 사용할 것이다.
ABCDE라는 행렬이 있을 때, 발생하는 모든 경우는
A(BCDE)
AB(CDE)
ABC(DE)
ABCD(E)
이렇게 된다. 재귀적으로 ABCD를 발생시키는 경우는
A(BCD)
AB(CD)
ABC(D)
이렇게 된다. 재귀적으로 ABC, ... 등도 동일하게 계산할 수 있다.
ABCD에 대해서 2차원 매트릭스를 DP로 사용하고 예를 들면,
그림의 1, 2, 3번에 대해서는 AB, BC, CD를 구하는것이니 바로 넘어가고 4, 5도 쉬우니 넘어간다.
(개인적으로 DP를 생각할 때 쉬운 케이스는 그냥 DP 공식을 생각 안하는 것이 나은 것 같다)
6번의 경우를 이용해서 DP식을 추정해볼 수 있는데,
ABCD를 구하기 위한 최소 연산은 (A)(BCD) or (AB)(CD) or (ABC)(D)의 경우이다.
이를 이용해서 DP식을 구하면 아래 사진의 빨간 글씨와 같다.
만약 i와 j가 같으면 0이고, 그 외의 경우엔 i~k까지 그리고 k+1~j까지의 DP 합과 같다. (이 때 k는 i와 j의 사이이다.)
추가적으로 i k j 번째 행렬을 곱한 연산을 추가적으로 더해야하므로 주황색으로 표시된 M[i][0] x M[k][1] x M[j][1] 부분을 더해주면 된다.
또한 이 연산이 반복적으로 DP[i][j]에 덮어씌워지기 때문에 min값을 계속해서 업데이트 해주면 된다.
DP식만 가지고 어떻게 for-loop을 돌아야하는지 범위를 생각하는게 쉽지 않을 수 있는데, 그냥 직접 for-loop을 풀어서 [0][2]에 해당하는 수식을 직접 적어보고, [1][1]에 해당하는 수식을 직접 적어보고, [0][3]에 해당하는 수식을 직접 적어보는 등으로 for-loop 범위조건을 찾으면 쉽다.
그림에서 생각해보면 1 -> 2 -> 3 / 4 -> 5 / 6 의 방식으로 for-loop을 돌 수 있도록 해주면 된
다.
사용한 테스트 케이스는 다음과 같다.
[[5, 3], [3, 10], [10, 6], [6, 8]] -> 444
[[20, 1], [1, 30], [30, 10], [10, 10]] -> 600
[[5, 3], [3, 10], [10, 6], [6, 8], [8, 5]] -> 519
코드는 아래와 같다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int dp[256][256];
int solution(vector<vector<int>> matrix_sizes) {
int answer = 0;
int size = matrix_sizes.size();
for(int i=0;i<size;i++)
for(int j=0;j<size;j++)
dp[i][j] = 1 << 30 - 1;
for(int i=0;i<size;i++)
dp[i][i] = 0;
for(int i=1;i<size;i++) {
for(int j=0;j<size - i;j++) {
int start = j;
int end = j + i;
for(int k=start; k<end; k++) {
dp[start][end] = min(dp[start][end],
dp[start][k] + dp[k+1][end] +
matrix_sizes[start][0] * matrix_sizes[k][1] * matrix_sizes[end][1]);
}
}
}
answer = dp[0][size - 1];
return answer;
}
