시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 512 MB 3756 1451 (39%) 1269
문제
$M \times N$ 크기의 행렬 $A$와 $N \times K$ 크기의 행렬 $B$의 행렬 곱셈 $AB$를 생각해보자. 두 행렬의 곱셈 과정의 연산 횟수는 $MNK$ 이다. 행렬 곱셈에는 교환 법칙 $AB = BA$는 성립하지 않지만, 결합 법칙 $(AB)C = A(BC)$는 성립한다. 결합 법칙에 의해 어떤 순서로 곱셈을 하는지에 따라 전체 연산 횟수가 차이난다. 예를 들어, 세 행렬 $A_{1}, A_{2}, A_{3}$가 있다고 하자. $A_{1}$은 $10 \times 100$ 크기, $A_{2}$는 $100 \times 5$ 크기, $A_{3}$은 $5 \times 50$ 크기의 행렬이다. $(A_{1}A_{2})A_{3}$ 순서로 곱셈을 할 경우, 전체 $10\times100\times5 + 10\times5\times50 = 7,500$번의 연산이 필요하고, $A_{1}(A_{2}A_{3})$ 순서로 곱셈할 경우, 전체 $100\times5\times50 + 10\times100\times50 = 75,000$번의 연산이 필요하다. $n$개의 행렬 $A_{1}, A_{2}, A_{3}, \dots, A_{n}$이 있다. 행렬 $A_{i}$의 크기는 $a_{i} \times a_{i+1}$이다. 이 때, $A_{1}A_{2}A_{3} \dots A_{n}$을 계산하는데 필요한 연산의 최소 횟수를 구하는 프로그램을 작성하라.
입력
첫 줄에 행렬의 개수 $n$이 주어진다. ($2 \leq n \leq 500$) 둘째 줄에 행렬의 크기를 나타내는 자연수 $n+1$개가 공백으로 구분되어 주어진다. $i$번째로 주어지는 수는 $a\_i$이다. ($a\_i \leq 100$)
출력
첫 줄에 $A_{1}A_{2}A_{3} \dots A_{n}$를 구하기 위해 필요한 연산의 최소 횟수를 출력한다.
힌트
#### 예제 입력 ``` 3 10 100 5 50 ``` #### 예제 출력 ``` 7500 ```