title: "[프로그래머스] 최적의 행렬 곱셈 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/12942"
description: "프로그래머스 Level 3 문제 [최적의 행렬 곱셈]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

def numop(r1, c1, r2, c2):
    return r1 * c1 * c2

def solution(matrix_sizes):
    M = matrix_sizes
    n = len(M)
    
    A = [[0] * n for _ in range(n)]
    # DP matrix의 i < j인 부분만 값을 채우는데,
    # d = j-i 의 값이 1, 2, ..., n-1 인 쌍의 순서대로
    # 값을 채웁니다.
    for d in range(1, n):
        for i in range(n):
            j = i + d
            if j >= n:
                break

            if d == 1:
                A[i][j] = numop(M[i][0], M[i][1], M[j][0], M[j][1])
            else:
                candidates = []
                for k in range(d):
                    # (1) i~i+k번째 행렬까지 최적으로 곱할 때의 연산 수와,
                    a = A[i][i+k]
                    # (2) i+k+1~j번째 행렬까지 최적으로 곱할 떄의 연산 수와,
                    b = A[i+k+1][j]
                    # (3) (i~i+k)번째 행렬곱과 (i+k+1~j)번째 행렬곱의 연산 수를
                    c = numop(M[i][0], M[i+k][1], M[i+k+1][0], M[j][1])
                    # 더한 값들을 비교해야 합니다. 후보 리스트에 넣고 최솟값을 구합시다.
                    candidates.append(a+b+c)
                # A[i][j] 는 후보 리스트 중 최솟값입니다.
                A[i][j] = min(candidates)
                
    return A[0][n-1]

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges