[백준] 11049_행렬 곱셈 순서 :: 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개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 
입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

---

아이디어

[백준] 11066_파일 합치기 문제의 풀이 아이디어를 적용할 수 있다.
<[백준] 11066_파일 합치기 :: Python> 포스팅 바로가기

• 행렬 A, B, C, D를 곱할 때 곱셈 연산 횟수를 구할 수 있는 케이스를 알아보자.

  • A * X1, (X1 = B*C*D)
  • X1 * X2, (X1 = A * B, X2 = C * D)
  • X1 * D, (X1 = A * B * C)

• dp[i][j] = i번째 행렬 ~ j번째 행렬을 곱할 때 곱셈 연산 횟수의 최소값이라고 할 떄,

• dp[i][j] = min { dp[i][k] + dp[k+1][j] + row[i] * col[k] * col[j] } for(i <= k < j)

  • 이때, dp[i][i]는 i번째 행렬 그 상태 그대로를 의미하므로 dp[i][i]에 저장되는 곱셈 연산 횟수는 0이다.

---

풀이

• 구현 시 유의할 점

  • 2차원 배열을 사용해서 dp를 진행하는데, 순회 시 오른쪽 아래 대각선 ↘️ 방향으로 진행하며 값을 채워간다.

• 코드 (pypy3)

import sys
input = sys.stdin.readline

n = int(input())
row = []
col = []
for _ in range(n):
    r, c = map(int, input().split())
    row.append(r)
    col.append(c)

# dp[i][j] = 행렬 i ~ 행렬 j를 곱셈할 때, 곱셈 횟수의 최소값
# dp[i][j] = min{ 
#     dp[i][k] + dp[k+1][j] + row[i] * col[k] * col[j] 
#     } for (i <= k < j)

dp = [[-1] * n for _ in range(n)]

for x in range(n):
    for i in range(n):
        j = i + x
        
        if j >= n:
            break

        if i == j:
            dp[i][j] = 0
        else:
            tmp = []
            for k in range(i, j):
                tmp.append(dp[i][k] + dp[k+1][j] + row[i] * col[k] * col[j])
            dp[i][j] = min(tmp)

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

---

참고 사이트