일단 문제 자체가 행렬곱연산을 알고 있다는 전제하에 만들어 진 것으로 보인다.
설명이 부족해도 너무나도 부족하다.

1. N by M 행렬과 M by K 행렬을 곱하면 N by K 행렬을 결과값으로 반환한다. 또한 연산 횟수는 N * M * K 가 된다.
2. 행렬은 결합법칙은 성립하지만, 교환법칙은 성립하지 않는다.

물론, 문제에서 연산을 예를 보여줄 때, 위의 두 가지의 규칙을 간접적으로 알려주었으나..
레벨3인 문제인 만큼 그런 것도 발견해서 알아서 하라는 의미인지는 모르겠다.

1번 규칙에 의해서 두 행렬을 곱하면, 두 행렬 사이에 끼어있는 중간에 같은 숫자가 날라가는 사실을 알고있다.
그래서 해당 부분을 어떻게든 모종의 순서대로 잘 날려보내면, 최적의 행렬 곱셈을 할 수 있지 않을까?
라고 생각할 수 있다. 그런데, 행렬곱을 잘만 생각해보면, 모든 행렬이 곱해져 하나의 행렬이 남을 때까지. 끝없은 곱의 연속이다.
과연, 가운데 값만 잘 제거한다고 행렬의 곱셈 연산 횟수가 낮아질까? 잘만 생각해도 아니지 않은가?
행렬 곱의 최소 곱 연산 횟수에 영향을 주는 요인은 단순히 가운데의 공통 값이 아니다. N * M * K 가 연산 횟수 결과인만큼.
모든 행렬의 요인이 서로서로 곱셈 연산 횟수에 영향을 끼친다.
그렇다. 해당 문제는 모든 경우를 파악해서 정답을 도출해내는 문제이다.

그럼, 모든 경우를 계산하려면, 어떻게 하는가?
간단하다. 2개씩 곱한 최소 연산 횟수, 3개씩 곱한 최소 연산 횟수, .... , n개씩 곱한 최소 횟수를 각각 구해보면,
마지막에 구하는 것이 결과가 되지 않겠는가?

예시를 하나 들어보자.
[4, 5], [5, 10] [10, 7], [7, 3]
예시에도 알 수 있는 인접한 두 행렬은 연결된 사이즈가 항상 같다는 것을 알 수 있다.
두 행렬을 곱해서 새로운 행렬이 나와도 그 법칙은 성립한다. 한 번 해보면 알 수 있다.

여기서 [4, 5] ~ [7, 3]을 모두 곱하려면 4개의 행렬을 곱한 최소 연산 횟수를 알아야 한다. 한 번 구해보자.

case1) 자기자신을 곱한경우.

• 곱할 것이 없다는 것을 알 수 있다. 자신 자신은 곱할 수 없으므로 최소 연산 횟수는 0이다.

case2) 인접한 행렬들의 곱.(2개의 행렬을 곱한 경우.)

• 인접한 행렬들을 각각 곱한다면, 그것보다 더 작은 최소연산 횟수는 그보다 더 작은 것이 불가능하다.
• 행렬의 교환법칙은 성립하지 않으므로, 두 행렬 간의 곱의 연산 방법은 하나 밖에 존재하지 않기 때문이다.

case3) 2칸 떨어진 행렬들의 곱.(3개의 행렬을 곱한 경우.)

• 인접한 행렬의 계산은 하나밖에 없지만, 3개 행렬의 연산은 결합법칙이 성립하여 1, 2, 3번 행렬이 존재한다면, (1, 2), 3 과 또는 1, (2, 3) 과 같이 묶어서 연산이 가능하다. 우리는 (1, 2)와 (2, 3)의 연산 결과를 case2에서 구했으므로, 비교하여 어떤 값이 더 작은지 알 수 있을 것이다. 이런 연산을 모든 경우의 수에 대해 하면 된다.

case4) 3칸 떨어진 행렬들의 곱. (4개의 행렬을 곱한 경우. 정답을 구하는 연산)

• 4개의 행렬의 곱을 구하는 것은 답을 구하는 것이다. 4개의 행렬도 마찬가지의 곱이 성립한다. 1, 2, 3, 4의 행렬이 존재한다면, 1, (2, 3, 4) 와 (1, 2, 3), 4 두 가지의 연산이 성립한다. 그런데 우리는 case3에 대해서, 3가지의 행렬들에 대한 곱에 대한 최소 연산 결과를 알고 있다. 마찬가지로 대입해서, 더 작은 값이 우리가 원하는 답이 된다.

위의 간단한 예시로 어느정도 이해가 가능했으면 좋겠다.
행렬을 곱하는 갯수를 0개 부터 N개 까지 순차적으로 늘려 최소 곱 연산 횟수를 구하는 방식이다.
메모리 낭비를 방지하기 위해 DP를 사용한 연산이라고 봐도 좋다.
우리가 무조건 아는 수부터 연산하고 한단계씩 경우의 수를 늘리면서 연산을 한다.

우린 여기에서 2차원 배열인 DP를 선언한다. 기본값은 0으로 한다.

DP = [[0 for i in range(len(matrix_sizes))] for j in range(len(matrix_sizes))]

위와 같이 간단히 파이썬 코드로 나타 낼 수 있을 것이다.

임의의 변수 a, b가 존재할 때,(a <= b 인 경우만)
DP[a][b] 의 의미는 a부터 b까지의 곱의 최소 연산 횟수가 된다.

만약 문제에서 제시한 matrix_sizes의 수가 4개일 경우(1, 2, 3, 4 행렬), 어떤식으로 값이 구해지는지 보자.

case1) 1개의 행렬을 곱하는 경우.
-아무 연산이 필요가 없다. 만약 python코드를 사용하지 않았다면,
DP[a][b] = 0 과 같은 연산을 수행하여 초기값을 셋팅해줄 수도 있다.

case2) 2개의 행렬을 곱하는 경우.

• (1, 2), (2, 3), (3, 4)의 행렬 연산을 수행한다. DP에 각각 최소 연산값을 계산한다. for문 돌려서 어떻게 a, b를 만들고 해당 원소에 접근 할 수 있을지 생각해본다.

case3) 3개의 행렬을 곱하는 경우.

• (1, (2, 3)), ((1, 2), 3), (2, (3, 4)), ((2, 3), 4)와 같이 행렬 연산을 수행한다. 여기서 부터는 괄호 안에 2개씩 묶인 값을 알고 있을 것이다. 해당 값을 이용해서 계산을 수행 할 수 있어야한다. 또한 (1, 2, 3) 과 (2, 3, 4)에 대해 괄호를 두 번씩 묶어서 연산하는 것을 알 수 있다. 여기서 제3의 for문이 필요하다는 사실을 유추해낼 수 있다.

case4) 4개의 행렬을 곱하는 경우.

• (1, (2, 3, 4)), ((1, 2), (3, 4)), ((1, 2, 3), 4) 와 같이 계산한다. 괄호에 묶어있던 값은 case2 ~ case3에서 계산했던 값이므로 충분히 알 수 있을 것이다.

여기서 이 모든걸 한 번에 해결해주는 점화식을 알려주겠다.
matrix_sizes를 m이라고 약칭함.

DP[a][b] = min(DP[a][b], DP[a][k] + DP[k+1][b] + (m[a][0] * m[k][1] * m[b][1]))

DP[a][b]를 구하려면 DP[a][b]와 DP[a][k]~ 와 비교하여 작은 값을 구하면 된다.
여기서 a와 b가 아닌 k가 나온다. k는 a~(b-1)까지를 for문으로 돌리는 변수다.
a에서 b구간을 1씩 늘리면서 돌리는 것이다.
DP[a][k] + DP[k+1][b] 는 a에서 k까지의 최소 곱 연산과 k+1 부터 b까지의 최소 곱 연산을 더한 것이다.
그리고 여기다가 이 최소 곱연산을 한 결과를 합치려면 k로 중간에 짤려진 부분부터 곱연산을 수행하여 다시 새로 더해주어야한다.
이해하는가? m by n 과 n by k를 연산하면 m by k 가되는 것을 이용하여, 위와 같은 연산이 가능해진다.
k의 역할은 두 행렬 곱사이에 중간에 하나씩 잘라다가 결합법칙을 만들어준다.
(1, (2, 3)) 연산을 이와 같이 할 경우는 k가 0일 경우.
((1, 2), 3) 이와 같이 할 경우는 k가 1인 경우이다.
즉, k를 하나씩 늘려가며 결합을 묶어서 최소 연산 횟수를 찾아내는 방식이다.
여기서 주의할 점은 처음 값이 0으로 지정되어 있으므로 DP[a][b]를 연산할 경우
초기 값으로, 충분히 크게 주고 연산을 시작해야한다.

마지막으로 전체적인 for문의 구조를 보여겠다.
n은 matrix_size의 길이라고 한다.

for(int i = 0; i < n; i++){ //최상단 for문 몇개의 행렬을 계산할지 정하는 변수이다. 곱할 두 행렬간의 간격이다.

    for(int j = 0; j < n-i; j++){ //행렬곱의 시작 행렬을 정하는 for문, j번 행렬부터 시작함.
        int a = j;  //j번째 행렬부터 시작함.
        int b = j + i;  //j부터 행렬의 개수 i를 더해주어 행렬곱의 범위를 다시 정해줌.

        for(int k = a; k < b; k++){ // k는 두 행렬간에 구간을 나누어 결합법칙을 만들어줌.
            //점화식 연산수행.
       }
    }
}

사실, 이건 프로그래밍과, 선형대수학의 기초를 담고있는 문제이다.
둘 중 하나라도, 지식이 부족하면 이해가 가기는 힘들 것이다.
최대한 이해하기 쉽도록 노력했으며, 그래도 어렵게 느껴진다면,
그건 어려운 것이 아니라, 낯설어서 그렇다. 반복적인 접촉은 익숙함을 만들어내니,
포기만 하지 말자.

야매로 작성한 글이라서, 오타 및 오류가 발생할 가능성이 100프로이므로 참고 봐주면 감사하겠다.

20000