알고리즘/백준
[백준] 11049번 행렬 곱셈 순서 (파이썬)
알감자
2022. 1. 4. 20:09
11049번: 행렬 곱셈 순서
첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같
www.acmicpc.net
코드
def solution(n, li):
dp = [[0 for _ in range(n)] for _ in range(n+1)]
for i in range(1, n):
for j in range(n-i):
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] + li[j][0] * li[k][1] * li[j+i][1])
print(dp[0][n-1])
n = int(input())
li = []
for _ in range(n):
li.append(list(map(int, input().split(" "))))
solution(n,li)