[백준] 11049 행렬 곱셈 순서

문제

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

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

입력

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

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

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

출력

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

 

 

---

풀이

 

https://claude-u.tistory.com/271#recentComments

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

을 분석했다.

 

행렬 X 행렬로 2차원 배열을 만들어야 한다.

dp[i][j]에는 i부터 j행렬의 곱셈 순서에 따른 여러 결과값 중 가장 작은 값이 저장된다.

 

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열)

)

 

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]) #맨 오른쪽 위

 

 

만약 ABCDE의 행렬이 입력된 경우이다.

주의할 점은 j는 대각선을 의미하고 i는 대각선으로부터의 거리를 뜻한다는것이다.

일반적인 2중포문을 훑는 방식이 아님!

인접한 행렬곱은 방법이 한가지이니 바로 저장한다.

i=3, j=1, k=2인 경우이다.

파란색 칸을 채우기 위해 분홍색 두 칸의 값을 더하고 거기에 두 행렬곱을 곱하는 비용을 더한다.

 

대박어렵다..