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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12942

프로그래머스

풀이

dp 문제이다. 따라서 문제 상황을 해결하기 위한 점화식을 세워야 한다.

일반적인 상황을 가정하고 이 상황을 해결하는 과정을 생각해 보면서 알맞은 점화식을 유도해 보자.

 

4개의 행렬 M1, M2, M3, M4가 있으며,  arr라는 배열은 arr[i][j]일 때, i 행렬부터 j 행렬까지의 곱을 수행할 때의 계산 수의 최솟값이라고 가정하자.

 

이런 상황에서 M1, ((M2, M3), M4)가 최적의 행렬 곱셈이라면, arr[1][3] = arr[1][2] + arr[3][3] + M2의 행 * M3의 열 * M4의 열이 된다. (물론 다른 상황에서는 arr[1][3]이 arr[1][1] + arr[2][3] + M2의 행 * M2의 열 * M4의 열이 될 수도 있다.)

이를 일반화하면 arr[i][k] + arr[k+1][j] + matrix_size[i][0] * matrix_size[k][1] * matrix_size[j][1]가 되는 것이다. 그리고 우리는 최솟값을 구해야 하기 때문에 최종적으로 가능한 k값을 순회하면서 기존의 값보다 작은지 확인하며 arr[i][j] = min(arr[i][j], arr[i][k] + arr[k+1][j] + matrix_size[i][0] * matrix_size[k][1] * matrix_size[j][1])을 구하면 되는 것이다.

def solution(matrix_sizes):    
    cnt = 0
    size = len(matrix_sizes)
    _MAX = int(10e9)
    
    arr = [[_MAX for _ in range(size)] for _ in range(size)] # 행렬곱을 위해 계산한 수를 저장할 배열
    for i in range(size): # 자기 자신과 행렬곱(arr[i][i])을 하는 경우는 없으므로 0으로 설정
        arr[i][i] = 0
    
    
    for i in range(size-1, -1, -1): # 행렬곱의 시작부분
        for j in range(i+1, size): # 행렬곱의 끝부분
            for k in range(i, j): # 행렬곱의 최소 계산하는 수를 알아내기 위해 순차적으로 탐색
                arr[i][j] = min(arr[i][j], arr[i][k]+arr[k+1][j]+matrix_sizes[i][0]*matrix_sizes[k][1]*matrix_sizes[j][1]) # 기존값과 k일때 새로운 값을 비교하여 최솟값을 저장
    
    return arr[0][size-1]