프로그래머스_python_최적의 행렬 곱셈

문제

https://programmers.co.kr/learn/courses/30/lessons/12942#

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

풀이

문제 접근하기

행렬곱셈에는 결합법칙이 성립하므로 행렬을 곱하는 순서에 따라 곱셈의 횟수가 달라진다.

dp를 사용해서 이 문제를 해결할 수 있다.

 

우선, N*N의 테이블을 작성한다. 테이블의 각 셀에는 아래에 해당하는 값을 적어 넣는다.

dp[시작][끝] = (시작~끝) 범위에 있는 행렬을 모두 곱할 때 최소 연산 수

 

sizes에 아래와 같은 행렬이 담겨 있다면, 

dp[3][8] 는 DEFGHI를 만들기 위한 최소 연산 수이고, 

DEFGHI를 만들 수 있는 경우의 수를 생각해보면, 아래와 같다.

	start	middle	end
D + EFGHI	3	3	8
DE + FGHI	3	4	8
DEF + GHI	3	5	8
DEFG + HI	3	6	8
DEFGH + I	3	7	8

그 중 DE + FGHI의 경우를 살펴보면, 필요한 연산의 수는

(DE 연산 수) + (FGHI 연산 수) + 4*3*3 = dp[3][4] + dp[5][8] + S[0]*M[1]*E[1]이다.

점화식 만들기

위의 식을 참고하여 점화식을 만들 수 있다.

(S~E까지 연산수) = (S~M까지 연산수) + (M+1~E까지의 연산수) + 두 행렬을 곱하기 위한 연산 수

dp[s][e] = min(dp[s][m]+dp[m+1][e] + sizes[s][0] + sizes[m][1] + sizes[e][1]), (s<=m<e)

TOP-DOWN

dp[3][8] = min(
dp[3][3] + dp[4][8] + sizes[3][0] + sizes[3][1] + sizes[8][1],
dp[3][4] + dp[5][8] + sizes[3][0] + sizes[4][1] + sizes[8][1],
dp[3][5] + dp[6][8] + sizes[3][0] + sizes[5][1] + sizes[8][1],
dp[3][6] + dp[7][8] + sizes[3][0] + sizes[6][1] + sizes[8][1],
dp[3][7] + dp[8][8] + sizes[3][0] + sizes[7][1] + sizes[8][1]
)

점화식에 따라 dp[3][8]을 위처럼 표현할 수 있다. 따라서, 대각선을 따라 dp를 채워나간다.

 

대각선 위쪽 방향으로 탐색

비슷한 문제

https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

코드

def solution(sizes):
    dp = [[0 for j in range(len(sizes))] for i in range(len(sizes))]
    
    for gap in range(1, len(sizes)) : 
        for s in range(0, len(sizes)-gap) : 
            e = s+gap
            
            candidate = list()
            for m in range(s, e) :
                candidate.append(
                    dp[s][m]+dp[m+1][e]+
                    sizes[s][0]*sizes[m][1]*sizes[e][1])
            dp[s][e] = min(candidate)
            
    return dp[0][-1]