프로그램 명: matrixprod
제한시간: 1 초

A 행렬이 m * k 행렬이고 , B 행렬이 k * n 행렬이면 두 행렬의 곱 A * B 는 m * n * k 번의 곱으로 구할 수 있다. 물론 두 곱이 가능하기 위해서는 A 행렬의 렬의 수 와 B 행렬의 행의 수가 동일해야 한다. 또한 결과 행렬은 m * n 행렬이 된다.

예를들어 , A 행렬이 2*4 행렬이고 , B 행렬이 4*3 행렬이면 두 행렬의 곱은 2*3*4 번의 곱으로 결과를 얻을 수 있다. 두 행렬의 곱으로 얻어지는 행렬은 2 * 3 행렬이 된다.

세 개의 행렬 (A * B) * C 와 A * (B * C) 는 동일하다. 즉, 무엇을 먼저 곱하든지 곱의 결과는 같다.

만약 A 행렬이 2 * 3 이고, B 행렬이 3 * 4 이고, C 행렬이 4 * 2 라면 (A * B) * C 로 행렬의 곱을 계산하면 총 곱의 수는 40(2*4*3 + 2*2*4) 이고 , A * (B * C) 이면 36(3*2*4 + 2*2*3) 으로 두 번째식이 곱을 적게한다.

우리가 해야할 문제는 여러개의 행렬의 크기가 주어질 때 , 최소 곱의 횟수를 구하는 문제이다.

입력 방법

입력의 첫째 줄에는 행렬의 수(2 <= N <= 100)가 주어지고 , 다음 줄에는 N+1개의 수가 주어진다. N 번째 수와 N+1 번째 수가 하나의 행렬의 크기를 의미한다. 입력의 오류는 없는 것으로 가정한다.

출력 방법

곱의 최소 횟수를 출력한다.

입출력 예

입력

5
2  5  3  6  4  9

출력

186

출처:
[질/답] [제출 현황] [푼 후(2)]
[ 채 점 ] [홈으로]  [뒤 로]