[Python 3] BOJ - 11049 "행렬 곱셈 순서"

 # 문제 링크 : https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

 

 # 풀이 :

 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍 문제라는 것과 x와 y번째 사이의 k라는 변수를 유도하는 것이라고 생각한다. 만일 문제로 주어진 행렬이 4개라고 가정하고, 각각의 행렬 정보가 A = 5 X 3, B = 3 X 2, C = 2 X 6, D = 6 X 7이라 하자. 곱한다는 것은 무조건 2개 이상의 행렬이 피연산자일 때만 가능하므로 아래 행렬 D의 대각선은 모두 0이 된다고 할 수 있다. 또한, 2개만 곱하는 경우는 1번째 행렬의 행 * 1번째(2번째) 행렬의 열(행) * 2번째 행렬의 열이다. 아래 2차원 행렬 D[i][j]를 i번째 행렬과 j번째 행렬을 곱할 때, 연산이 최소가 되는 횟수라고 정의하자.

	0	1	2	3
0	0	30	?	?
1		0	36	?
2			0	84
3				0

<표 1. N = 4인 경우 배열 D>

 

<그림 1. D[0][2] 예시>

  위의 그림과 같이 D[0][2]를 채우는 법은 3가지가 있다. 사실 1)과 3)은 같다. 따라서 2가지가 있다. 그런데 이미 (B * C)는 D[1][2]에, (A * B)는 이미 D[0][1]에 있다. 따라서, D[0][2] = min(30 + 5 * 2 * 6, 36 + 5 * 3 * 6)이므로 90이 된다. 똑같은 논리로 D[1][3]도 채울 수 있다.

	0	1	2	3
0	0	30	90	231?
1		0	36	126
2			0	84
3				0

<표 2. N = 4일때 배열 D>

 그렇다면 D[0][3], 즉 A * B * C * D의 연산 최솟값은 D[0][2]를 채울 때의 논리 처럼 D[0][2]와 D[1][3]의 관계로 채워질 수 있을까? 결론은 그렇지 않다.

<그림 2. D[i][j] 예시>

  i부터 j까지 곱하는 경우를 생각할 때, 그 사이에 먼저 곱하는 행렬이 존재할 수도, 그렇지 않을 수도 있다. 존재하지 않는다면 k는 항상 i과 같거나, j와 같아야 한다. 그런데, 존재한다면 어디서 존재하는 지를 알아야 하는데, 이는 불가능하다. 따라서 먼저 곱해지는 행렬의 위치를 또다른 변수 k로 놓는다면, 항상 i와 j의 곱하는 연산의 최소값은 i와 k까지의 연산의 최소값 + k + 1과 j까지의 연산의 최소값이라 할 수 있다.

 따라서 D[0][3]은 k가 0,1,2가 될 수 있으며, 표 2처럼 D[0][2]를 채우는 논리만 적용한다면, k가 0,2일때만 D[0][3]의 경우를 구하는 것이므로 k의 모든 경우에 대해 D[0][3]의 값을 갱신할 수 없다. 이 경우 k가 1인 경우가 최소이며 D[0][3]은 231이 아니라 184이다.

	0	1	2	3
0	0	30	90	184
1		0	36	126
2			0	84
3				0

<표 3. N = 2일때 올바른 배열 D>

 

결과적으로 matrix가 각 행렬의 행과 열을 저장하는 2차원 배열이라고 정의할 때, 점화식은 다음과 같다.

 

 # 코드(반복문으로 작성한다면 인덱스를 고려해야 해서 재귀로 작성하였다. 물론 Bottom-Up(반복문)도 가능하다.)

import sys
n = int(sys.stdin.readline())

# matrix : (임의의 행렬 A의 행, 임의의 행렬 A의 열)을 각 원소로 갖는 배열
matrix = []
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    matrix.append((a,b))

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

# go : 점화식을 이용한 Top-Down 방식 DP
def go(x,y):
    # 이미 d[x][y]를 구했으면 Memoization을 통해 리턴
    if d[x][y] != -1:
        return d[x][y]
    # 곱셉은 최소 2개의 행렬이 있어야 하므로 만약 x와 y가 같다면
    # '곱셉을 할 수 없다'는 의미의 0을 리턴
    if x == y:
        return 0
    # 2개의 행렬만을 곱하는 경우는 단순히 matrix의 정보를 이용한다
    if x + 1 == y:
        return matrix[x][0] * matrix[x][1] * matrix[y][1]
    # 위의 모든 경우가 아니라면 k를 i ~ j - 1까지 움직여 d[i][j] 갱신
    for k in range(x, y):
        left = go(x, k)
        right = go(k + 1, y)
        if d[x][y] == -1 or d[x][y] > left + right + matrix[x][0] * matrix[k][1] * matrix[y][1]:
            d[x][y] = left + right + matrix[x][0] * matrix[k][1] * matrix[y][1]
    return d[x][y]

print(go(0,n - 1))