[백준11049번] 행렬 곱셈 순서 / Python3

문제

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

입력

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

예제 입력 1

3
5 3
3 2
2 6

예제 출력 1

90

나의 풀이

11066번 파일 합치기문제와 비슷한 문제이다. 11066번 문제에서는 인접한 페이지들의 합을 누적하여 psum이라는 배열에 저장을 해두었었다. 이 문제에서는 다르게 i번째와 j번째까지의 최솟값을 구해나가면서 중간의 k를 가지고 차수들을 곱해 최솟값을 구하면된다.

따라서 점화식으로는 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + dim[i][0]*dim[k][1]*dim[j][1])이 된다. i ~ k, k+1 ~ j구간의 값들을 구해 각각의 dim값을 곱해주어 더해주어야한다. 예를들어 A = 5x3, B = 3x2, C = 2x6이 있는데 i가 1, j가 3인 상황에서 k가 1이라면 dim[i][0] = 5, dim[k][1] = 3, dim[j][1] = 6으로 A(BC)이 되고, k가 2라면 dim[i][0] = 5, dim[k][1] = 2, dim[j][1] = 6으로 (AB)C인 경우가 된다.

이렇게 다이나믹 프로그래밍 기법을 사용하여 문제를 해결할 수 있다.

코드

# 11049번 행렬 곱셈 순서
import sys

# main
n = int(sys.stdin.readline())

dim = [[0,0]]
for _ in range(n):
    tmp = [int(x) for x in sys.stdin.readline().split()]
    dim.append(tmp)

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for dia in range(n):
    for i in range(1, (n - dia) + 1):
        j = i + dia

        if i == j:
            continue

        dp[i][j] = 987654321
        for k in range(i,j):
            dp[i][j] = min(dp[i][j], 
                           dp[i][k] + dp[k+1][j] + (dim[i][0] * dim[k][1] * dim[j][1]))

print(dp[1][n])