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

문제

• 크기가 5 by 3인 행렬 A, 크기가 3 by 10인 행렬 B, 크기가 10 by 6인 행렬 C가 있을 때, 순서대로 A와 B를 먼저 곱하고, 그 결과에 C를 곱하면 A와 B행렬을 곱할 때 150번을, AB 에 C를 곱할 때 300번을 연산을 해서 총 450번의 곱하기 연산을 한다.
• 행렬이 N개 주어질 때, 모든 행렬을 곱하기 위한 최소 곱셈 연산의 수를 리턴하기
• 3 <= N <= 200

 

풀이

• 중간 숫자가 큰 것 먼저 해치워야 한다고 생각하고, 행 또는 열을 기준으로 정렬해서 찾으려고 시도 -> 실패
• 모든 경우의 수를 살펴보는 것으로 변경 
  • 약 O(N*N*N) = 200*200*200 = 8000000 이므로 가능하다.

 

def solution(matrix_sizes):
    n = len(matrix_sizes)
    M = matrix_sizes
    
    # dp[i][j] : i ~ j번째까지의 행렬 곱셈을 할 때 최소의 연산 수
    dp = [[0]*n for _ in range(n)]
    
    # 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 :         # 첫 번째 행렬 곱셈이 된 경우
                dp[i][j] = M[i][0] * M[i][1] * M[j][1]
            else :              
                candidates = [] # 모든 경우의 수를 구한 뒤 최솟값 찾기
                for k in range(d) :
                    # i ~ i+k 행렬까지 최소의 곱셈연산 수
                    # i+k+1 ~ j 행렬까지 최소의 곱셈연산 수
                    # (i~i+k) * (i+k+1~j) 두 행렬의 곱셈 연산 수
                    candidates.append(dp[i][i+k] + dp[i+k+1][j] + M[i][0] * M[i+k][1] * M[j][1]) 
                dp[i][j] = min(candidates)
                
    return dp[0][n-1]

 

References

• 프로그래머스 Lv3