#220 백준 파이썬 [11049] 행렬 곱셈 순서

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

 

Solution

파이썬으로는 느려서 풀지 못한다. pypy3로 풀 수 있는 문제

 

코드는 복잡해보이지만 은근히 간단하다.

우선 DP로 2차 행렬을 만들고 시작한다.

ABCDE 까지 5개의 행렬이 있다고 생각해보자.

각각 (5, 7) (7,3) (3, 9) (9, 11) (11, 2) 라고 가정해보자.

 

새로운 dp라는 행렬을 만들어준다.

여기서 행과 열은 오른쪽 위만 쓴다.

각 칸의 의미는 i행렬부터 j행렬까지 행렬 곱의 최소값이다.

	A	B	C	D	E
A
B
C
D
E

 

1. 먼저 각 행렬이 같은 부분에 0을 입력해준다.

	A	B	C	D	E
A	0
B		0
C			0
D				0
E					0

 

2. A~B, B~C 등 1칸 차이가 나는 행렬들은 그냥 곱해주는것과 마찬가지이므로 곱한 값을 바로 대입해준다.

	A	B	C	D	E
A	0	105
B		0	189
C			0	297
D				0	198
E					0

 

3. 이후 두칸 이상 떨어진 행렬들의 곱의 최솟값은 다음과 같다. 

 

의사 코드 풀이)

 

ABCDE연속행렬 곱의 최솟값 =

min(ABCDE,

min(A) + min(BCDE) + 합치는 비용(A행 * A열 * E열),

min(AB) + min(CDE) + 합치는 비용(A행 * B열 * E열),

min(ABC) + min(DE) + 합치는 비용(A행 * C열 * E열),

min(ABCD) + min(E) + 합치는 비용(A행 * D열 * E열)

)

 

옆 행렬을 곱하는 것을 시작으로 계속해서 거리가 큰 행렬을 산출한다.

마지막엔 거리가 제일 긴, 처음부터 끝까지의 행렬을 구할 수 있다.

 

식)

dp[첫행렬 위치][k] + dp[k+1][마지막 행렬 위치] + ( matrix[첫행렬 위치][0] * matrix[k][1] * matrix[마지막행렬 위치][1] )

k는 첫행렬 부터 마지막 행렬-1 까지 for문 순회한다.

 

정답)

	A	B	C	D	E
A	0	105	240	567	364
B		0	189	528	294
C			0	297	252
D				0	198
E					0

 

Python Code

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


for i in range(1, N): #몇 번째 대각선?
    for j in range(0, N-i): #대각선에서 몇 번째 열?
    
        if i == 1: #차이가 1밖에 나지 않는 칸
            dp[j][j+i] = matrix[j][0] * matrix[j][1] * matrix[j+i][1]
            continue
        
        dp[j][j+i] = 2**32 #최댓값을 미리 넣어줌
        for k in range(j, j+i): 
            dp[j][j+i] = min(dp[j][j+i], 
                             dp[j][k] + dp[k+1][j+i] + matrix[j][0] * matrix[k][1] * matrix[j+i][1])
                
    
print(dp[0][N-1]) #맨 오른쪽 위