[백준]11049번 행렬 곱셈 순서(python 파이썬)

저번 풀이에 이어 dp의 대표적인 문제를 하나 풀어보겠습니다!

참고로 pypy3으로 제출해야 합니다!

문제

11049번: 행렬 곱셈 순서

 

 

아이디어

행렬이 A, B, C, D가 있다고 가정해봅시다

행렬 곱셈 연산 경우의 수는 다음과 같습니다

A(BCD) -> A((BC)D)

           -> A(B(CD))

(AB)(CD)  

(ABC) D -> (A(BC))D

           -> ((AB) C))D

 

 

규칙 발견

행렬 i번째에서 j까지의 연산을 계산하기 위해서는

dp[i][j]는 행렬 i에서 j까지의 곱셈 연산 수를 의미합니다.

dp[i][j]의 값은 이 수식들 중 가장 작은 값입니다.

dp[i][i+0] + dp[i+1][j]  + A[i][0]*A[i+1][0]*A[j][1]

dp[i][i+1] + dp[i+2][j]  + A[i][0]*A[i+2][0]*A[j][1]           

                   .......

dp[i][j-2] + dp[j-1][j] + A[i][0]*A[j-2][0]*A[j][1]

dp[i][j-1] + dp[j][j] + A[i][0]*A[j-1][0]*A[j][1]

 

이를 코드로 나타내면 다음과 같습니다.

 

for  i in range(n-1,-1,-1):
    for j in range(i+1,n):
        dist = j-i
        for k in range(dist):
            dp[i][j] = min(dp[i][j],dp[i][i+k]+dp[i+k+1][j]+A[i][0]*A[i+k][1]*A[j][1])

 

 

전체 코드

import sys

input = sys.stdin.readline
INF = sys.maxsize

n = int(input())
A = []
for _ in range(n):
    r,c = map(int,input().split())
    A.append((r,c))
dp = [[INF for _ in range(n)] for _ in range(n)]
for i in range(n):
    dp[i][i] = 0
# dp[i][j] = i에서 j까지 연산할 때의 최소 연산
for  i in range(n-1,-1,-1):
    for j in range(i+1,n):
        dist = j-i
        for k in range(dist):
            dp[i][j] = min(dp[i][j],dp[i][i+k]+dp[i+k+1][j]+A[i][0]*A[i+k][1]*A[j][1])
print(dp[0][-1])

잘못된 내용이 있으면 피드백 부탁드립니다!

궁금한 내용이 있으면 언제든지 물어보세요!!!