[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의 맨 마지막 위치 & 두번째 원소.

 

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

 

 

 

	import math
	def solution(matrix_sizes):
	# table[start][end] = 인덱스 start ~ end 까지의 연산 최솟값.
	table = [[math.inf for _ in range(len(matrix_sizes))] for _ in range(len(matrix_sizes))]
	# start와 end가 동일한 경우는 연산하지 않으므로 0으로 설정.
	for idx in range(len(matrix_sizes)):
	table[idx][idx] = 0
	for gap in range(1, len(matrix_sizes)):
	for start in range(len(matrix_sizes)):
	end = start + gap
	if end >= len(matrix_sizes):
	break
	for sep in range(start, end):
	table[start][end] = min(
	table[start][end],
	table[start][sep] + table[sep+1][end] + (matrix_sizes[start][0] * matrix_sizes[sep][1] * matrix_sizes[end][1])
	)
	return table[0][-1]

view raw [프로그래머스] 최적의 행렬 곱셈.py hosted with ❤ by GitHub