Baekjoon 11049. 행렬곱셈순서 / Python

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

문제 설명

주어진 여러 개의 행렬을 순서대로 곱할 때, 필요한 곱셈 연산의 최소 횟수를 구하는 문제
행렬의 곱셈 연산 수는 행렬을 곱하는 순서에 따라 달라지기 때문에, 최적의 곱셈 순서를 찾는 것이 중요하다.

알고리즘 및 코드 설명

알고리즘 설명

1. DP : dp[i][j] : i부터 j 까지의 행렬을 곱하는 데 필요한 최소 곱셈 연산 수코드 설명
2. DP 테이블 채우기:
   • 간격(interval)을 1부터 n−1n-1n−1까지 변화시키며, 각 간격에 대해 start와 end를 설정.
   • start부터 end까지의 최소 연산 수를 찾기 위해 mid를 사용하여 분할 정복.
   • dp[start][mid]와 dp[mid+1][end]의 연산 수와 추가적으로 두 부분 행렬을 곱하는 연산 수를 합산하여 최소값을 갱신.
3. dp[0][n-1]에 최종 결과가 저장됨.

시간복잡도

최악의 경우 O(N ^ 3) n < 500 이므로 충분함.

import sys
input = sys.stdin.readline

n = int(input())
arr = []
# dp[i][j] = i부터 j까지 곱연산 수의 최솟값
dp = [[10 ** 10] * n for _ in range(n)]
for i in range(n):
    r, c = map(int, input().split())
    arr.append([r, c])
# 자기 자신과는 연산 없음
for i in range(n):
    dp[i][i] = 0

# 간격마다 dp 실행
def min_multiple():
    for interval in range(1, n):
        for start in range(n - interval):
            end = start + interval
            for mid in range(start, end):
                # start부터 mid까지의 행렬 곱과 mid+1부터 end까지의 행렬 곱을 합산
                tmp = dp[start][mid] + dp[mid + 1][end] + arr[start][0] * arr[mid][1] * arr[end][1]
                # 최솟값 갱신
                dp[start][end] = min(dp[start][end], tmp)

# 최소 곱연산 수 계산
min_multiple()
print(dp[0][n - 1])