[Python] 11049 행렬 곱셈 순서

💻 문제 정의

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오.

💡 접근 및 설계

다이나믹 프로그래밍 방식으로 접근하였다. 주어진 행렬의 크기 배열에서, 해당 배열의 인덱스 만큼 까지 연산하였을 때 최솟값을 DP테이블에 저장하는 방식을 생각하였다.

N = 3, arr = [[5, 3], [3, 2], [2, 6]] 일때 최종적으로 dp[0][2]에 우리가 출력해야할 최솟값이 저장될 것이다.

dp[0][2] = min(dp[0][0] + dp[1][2] + 행렬곱 연산 횟수, dp[0][1] + dp[2][2] + 행렬곱 연산 횟수) ⇒ $min(A \cdot (BC), (AB) \cdot C)$ 으로 표현할 수 있다.

✏️ 알고리즘 풀이

INF = 2**31

dp = [[INF] * N for _ in range(N)]

for i in range(N):
    dp[i][i] = 0

DP테이블을 INF 값으로 초기화 해준다. dp[i][i] 부분은 자기자신 행렬곱 연산이므로 0을 넣어준다.

for i in range(1, N):
    for j in range(N-i):
        for k in range(j, j+i):
            temp = dp[j][k] + dp[k+1][j+i] + (matrix[j][0] * matrix[k][1] * matrix[j+i][1])
            dp[j][j+i] = min(dp[j][j+i], temp)

3중 반복문을 통해 DP 로직을 구현할 수 있었다.

i : dp를 구할 범위를 지정

j : 구하고 싶은 dp의 시작 인덱스

k : 서브 행렬로 쪼갤 기준점

dp[0][2]에서 k=1이면 dp[0][1] + dp[2][2] k=0이면 dp[0][0] + dp[1][2]

matrix[j][0] * matrix[k][1] * matrix[j+i][1] : 행렬 연산 횟수. 즉, [5, 3], [3, 2] 두 개의 행렬을 연산한다고 하였을 때, dp[0][1] = ~~~ + (5 * 3 * 2) 가 된다.

🗒️ 최종 제출 코드 (PyPy3 제출)

# 11049 행렬 곱셈 순서

import sys
input = sys.stdin.readline

INF = 2**31

N = int(input())

matrix = []
for _ in range(N):
    matrix.append(list(map(int, input().split())))

dp = [[INF] * N for _ in range(N)]

for i in range(N):
    dp[i][i] = 0

for i in range(1, N):
    for j in range(N-i):
        for k in range(j, j+i):
            temp = dp[j][k] + dp[k+1][j+i] + (matrix[j][0] * matrix[k][1] * matrix[j+i][1])
            dp[j][j+i] = min(dp[j][j+i], temp)

print(dp[0][N-1])

---

💭 오늘의 회고

-