[Python] 프로그래머스. 최적의 행렬 곱셈 (Level 4)

programmers.co.kr/learn/courses/30/lessons/12942

코딩테스트 연습 - 최적의 행렬 곱셈

DP문제. 이전에 풀었던 백준 파일합치기 문제와 로직은 동일하다.

[Python] 백준 11066. 파일 합치기

matrix를 문제 예시대로 [[5,3],[3,10],[10,6]] 으로 정의하고,

table[start][end] = matrix의 start index부터 end index까지 행렬곱셈 연산의 최솟값이라고 정의하자.

start == end인 경우, 행렬연산이 불가능하므로 table값을 0으로 설정한다.

 

예컨대 table[0][2]를 구한다면,

table[0][2] = min(
	table[0][분할기준점 0] + table[분할기준점 0 + 1 = 1][2] + (matrix[0][0] * matrix[분할기준점][1] * matrix[2][1]),
    table[0][분할기준점 1] + table[분할기준점 1+1 = 2][2] + (matrix[0][0] * matrix[분할기준점][1] * matrix[2][1])
)

형태가 된다. 

 

연산처리를 하기 위한 분할 기준점 index를 0으로 둘 경우, [3,10][10,6]은 이미 연산이 끝났고, 연산 결과 행렬은 [3,6] 이 된다.

분할 기준점까지의 행렬은 [5,3] 이므로, [5,3]과 [3,6]을 연산해야 한다.

따라서 필요한 값은 5, 3, 6이다.

matrix에서 5, 3, 6이 어느 위치에 있는 값인지 확인해보면,

 

5는 연산하려는 matrix의 맨 첫번째 위치 & 첫번째 원소

3은 연산하려는 matrix의 분할기준점 & 두번째 원소. (논리적으로는 분할기준점 바로 다음 행렬의 첫번째 원소이지만, 분할기준점의 두번째 원소와 값이 같다.)

6은 연산하려는 matrix의 맨 마지막 위치 & 두번째 원소.

 

따라서 이 위치값을 토대로 점화식을 구하면 된다.