[BOJ] 11049번: 행렬 곱셈 순서

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


전형적인 DP 문제입니다. D[i][j]를 matrix[i:j]를 곱할 때 필요한 최소 연산 수라고 할 때, sep = i+1~j-1에 대해 D[i][j] = min(D[i][sep]+D[sep][j]+matrix[i]의 row*matrix[sep]의 row*matrix[j]의 col) 이 됩니다.


O(N^3)에 해결이 가능합니다.


https://github.com/blisstoner/BOJ/blob/master/11049.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 1943번: 동전 분배  (2) 2018.03.24
[BOJ] 6986번: 절사평균  (0) 2018.03.22
[BOJ] 10835번: 카드게임  (4) 2018.03.20
[BOJ] 1509번: 팰린드롬 분할  (0) 2018.03.20
[BOJ] 5557번: 1학년  (0) 2018.03.20
[BOJ] 1036번: 36진수  (0) 2018.03.16
  Comments