문제 설명
크기가 a by b인 행렬과 크기가 b by c 인 행렬이 있을 때, 두 행렬을 곱하기 위해서는 총 a x b x c 번 곱셈해야합니다.
예를 들어서 크기가 5 by 3인 행렬과 크기가 3 by 2인 행렬을 곱할때는 총 5 x 3 x 2 = 30번의 곱하기 연산을 해야 합니다.
행렬이 2개일 때는 연산 횟수가 일정 하지만, 행렬의 개수가 3개 이상일 때는 연산의 순서에 따라서 곱하기 연산의 횟수가 바뀔 수 있습니다. 예를 들어서 크기가 5 by 3인 행렬 A, 크기가 3 by 10인 행렬 B, 크기가 10 by 6인 행렬 C가 있을 때, 순서대로 A와 B를 먼저 곱하고, 그 결과에 C를 곱하면 A와 B행렬을 곱할 때 150번을, AB 에 C를 곱할 때 300번을 연산을 해서 총 450번의 곱하기 연산을 합니다. 하지만, B와 C를 먼저 곱한 다음 A 와 BC를 곱하면 180 + 90 = 270번 만에 연산이 끝납니다.
각 행렬의 크기 matrix_sizes 가 매개변수로 주어 질 때, 모든 행렬을 곱하기 위한 최소 곱셈 연산의 수를 return하는 solution 함수를 완성해 주세요.
제한 사항
- 행렬의 개수는 3이상 200이하의 자연수입니다.
- 각 행렬의 행과 열의 크기는 200이하의 자연수 입니다.
- 계산을 할 수 없는 행렬은 입력으로 주어지지 않습니다.
풀이
문제는 간단하지만 이해하고 풀기 굉장히 어려운 문제이다.
문제를 요약하자면 주어진 행렬들을 모두 곱하는 연산 수를 최소로 만들면 몇 번의 연산이 필요한지 구하면 된다.
우선, 문제를 풀기 위해서는 행렬에 대한 기본 지식이 필요하다.
[a, b] 행렬과 [b, c]행렬을 연산하면 [a, c]라는 행렬이 결과로 나온다.
이때, 필요한 연산은 a * b* c이다.
즉, 가운데 겹치는 b를 한번만 사용하여 모두 곱한 것과 같다.
처음에는 이러한 성질을 이용하여 가운데를 큰 것부터 제거하면 답을 구할 수 있다고 생각할 수 있지만 이러한 접근이 항상 최적해를 보장하지 않는다.
정답을 구하기 위해서는 DP를 이용해야 한다.
DP에서 관리하는 값은 연산의 최솟값이다.
그렇다면 DP에 저장할 기준이 필요하다.
DP에 저장할 기준은 a부터 b까지 행렬을 곱하는데 필요한 최소 연산수이다.
즉, DP[a][b]라면 a부터 b까지 모두 곱하는데 필요한 연산의 최솟값이 된다.
그렇다면 DP를 모두 채우고 DP[0][n-1]을 return 하면 된다.
DP를 채우는 방법은 2개의 행렬을 곱하는데 필요한 연산을 살펴보면 쉽게 찾을 수 있다.
우선, a: [5,3], b: [3,10]의 경우를 봐보자.
두 행렬의 곱을 구하는 연산은 단 한가지이다.
- 5 * 3 * 10
이를 수식으로 나타내면, a[0] * b[0] * b[1]이다.
물론, a[0] * a[1] * b[1]도 동일하지만 행렬의 개수가 늘어나면 결과가 달라진다.
그럼 행렬이 3개인 경우를 봐보자.
a: [5,3], b: [3,10], c: [10,6] 일 때, abc행렬을 구하는 방법은 총 2가지이다.
- (ab)c
- a(bc)
첫 번째 경우의 연산을 계산해 보면 다음과 같다.
(ab)의 연산 수는 위에서 구했듯이 5 * 3 * 10이다.
이 연산의 결과로 [5, 10]의 행렬이 생기고 이를 [10, 6]과 다시 한번 곱하면 5 * 10 * 6번의 연산을 더 해야 한다.
즉, (5 * 3 * 10) + (5 * 10 * 6)번의 연산이 필요하다.
두 번째 경우는 다음과 같다.
bc를 곱한 연산은 3 * 10 * 6, 이를 다시 a와 곱하는 연산은 5 * 3 * 6 번이 필요하다.
총 (3 * 10 * 6) + (5 * 3 * 6) 번의 연산이 필요하다.
이를 통해 유추해 보면, 다음과 같은 점화식을 세울 수 있다.
DP[a][b] = DP[a][k] + DP[k+1][b] + (matrix[a][0] * matrix[k+1][0] * matrix[b][1])
k는 행렬의 곱을 끊는 위치이다.
k가 필요한 이유는 어떠한 순서로 행렬을 곱하는지에 따라 연산의 수가 달라지기 때문이다.
위에서 봤듯이 (ab)c와 a(bc)의 연산의 수가 다르다.
(ab)c는 DP[a][b] + DP[c][c]이고 a(bc)는 DP[a][a] + DP[b][c]인 것이다.
따라서, k번 행렬을 나눠보고 최솟값을 구하는 것이다.
점화식을 설명하자면 두 가지 부분으로 나눌 수 있다.
- DP[a][k] + DP[k+1][b]: (a부터 k까지 최소 연산수) + (k+1부터 b까지의 최소 연산수)
- matrix[a][0] * matrix[k+1][0] * matrix[b][1]: [a[0], k[1]] * [k+1[0], b[1]]의 연산 수
정리하자면 다음과 같다.
- a부터 b까지의 행렬의 곱에 필요한 최소 연산 수를 관리하며 DP를 채워 나간다.
- a와 b가 붙어있는 경우가 아니라면 a부터 b까지의 행렬을 곱하는 경우가 많다.
- 따라서, 여러 번 나눠보며 최솟값을 계산한다. (나누는 부분을 k라고 한다)
- 이때, 이전에 계산해 놓은 DP[a][k]와 DP[k+1][b]를 통해 [a[0], k[1]], [k+1[0], b[1]] 두 개의 행렬을 만들고 이 두 개의 행렬을 곱할 때 필요한 연산 수인 matrix[a][0] * matrix[k+1][0] * matrix[b][1]를 더해 준다.
전체 코드
#include <string>
#include <vector>
#include <iostream>
#include <climits>
using namespace std;
int solution(vector<vector<int>> matrix_sizes) {
int answer = INT_MAX;
int size = matrix_sizes.size();
vector<vector<int>> dp(size, vector<int>(size, 0));
for(int i = 0 ; i < size ; i++) dp[i][i] = 0;
for(int i = 1 ; i < size ; i++)
{
int b;
for(int a = 0 ; a < size ; a++)
{
b = i + a;
if(b >= size) break;
dp[a][b] = INT_MAX;
for(int k = a ; k < b ; k++)
{
dp[a][b] = min(dp[a][b], dp[a][k] + dp[k+1][b] + (matrix_sizes[a][0] * matrix_sizes[k+1][0] * matrix_sizes[b][1]));
}
}
}
return dp[0][size-1];
}