백준 11049번 : 행렬 곱셈 순서 in Python

11049번: 행렬 곱셈 순서

 

www.acmicpc.net

위 문제는 앞서 풀었던 11066번 문제(파일 합치기)와 매우 유사한 문제이다. 문제 풀이 알고리즘은 같으나 약간의 차이가 있다면 최소값을 구할 때 각 경우에 대한 값을 구하는 방법일 것이다.

파일 합치기 문제와는 달리 행렬 곱셈 순서의 경우 n개의 행렬을 곱한 결과의 곱셈 연산 횟수의 최소값은 k개의 행렬을 곱한 결과에서의 최소값과 n-k개의 행렬을 곱한 결과에서의 최소값을 더하고, 여기에 k개의 행렬을 곱했을 때 나오는 행렬의 크기와 n-k개의 행렬을 곱했을 때 나오는 행렬의 크기에 따라 나오는 곱셈 연산 횟수를 추가로 더한다. 그리고 그 값이 k가 1~n-1일 때 전부 구한 뒤 그들 중 최소값을 구한다.(k=1, n-1인 경우 1개의 행렬을 곱하는 경우는 없으므로 1개의 행렬을 곱한 결과에서의 최소값은 0으로 한다.)

이것만 주의한다면 11066번 문제와 별 차이 없다.

코드는 다음과 같다.

N = int(input())
arr = []
for _ in range(N):
    n, m = map(int, input().split())
    arr.append([n, m])
mat = [[0]*N for _ in range(N)]
for i in range(N-1):
    mat[i][i+1] = arr[i][0] * arr[i][1] * arr[i+1][1]
for d in range(3, N+1):
    for i in range(N-d+1):
        j = i+d-1
        arr2 = [mat[i][k] + mat[k+1][j] + arr[i][0]*arr[k][1]*arr[j][1] for k in range(i, j)]
        mat[i][j] += min(arr2)
print(mat[0][N-1])