백준 11049

행렬 곱셈 순서의 문제

행렬 A, B, C 등 여러 개의 행렬을 곱해서 최소값을 찾는 문제이다.

문제의 예로는 

A = 5x3 , B = 3x2, C= 2x6이 제시되었고 

행렬의 특성상 (A B)C와 A(B C)의 계산이 다르다. 제시된 행렬의 순서는 지켜야 하지만 곱의 순서는 정해야 하는 문제

행렬의 수가 최대 500개 정도 주어지는 데 하나하나 풀기는 어렵다

저번주에 풀었던 11066번 파일 합치기와 상당히 비슷했다.

그러므로 동적계획법 방식으로 구간의 곱셈 최솟값을 구해 구간을 넓혀가는 방식으로 풀었다.

 

11066이나 11049 같은 문제들은 주어진 수를 순서를 바꾸지 못하지만 곱의 순서는 정하는 방식으로 구간 곱셈의 최솟값을 생각해야겠다.

 

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

11049번: 행렬 곱셈 순서