2016 Java Chapter 8 (Week 08)

From: 2016-09-01 00:00:00 To: 2016-11-30 00:00:00 Now: 2024-11-21 21:59:35 Status: Public

C - 대수: 행렬 곱2 (난이도:고급)

Time Limit: 1s Memory Limit: 128MB

Submissions: 954 Solved: 251

Description

n개의 행렬을 서로 곱할때는 곱하는 순서에 따라 곱셈의 횟수가 달라지곤 한다. 예를 들어 행렬 A의 크기가 10 × 30 이고, 행렬 B의 크기가 30 × 5 이고, 행렬 C의 크기가 5 × 60 라고 하자. (AB)C와 A(BC)를 계산하는데 필요한 곱셈의 횟수는 다음과 같다.

(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000

여러분은 n개의 행렬의 크기를 입력받아, n개의 행렬을 모두 곱하는데 필요한 곱셈의 최소 횟수를 구하는 프로그램을 작성해야한다.

Input

* Line 1 : 행렬의 개수 n (1~1,000)

* Line 2 ~ n+1 : 행의_개수 열의_개수

- 모든 개수는 정수이며 범위는 1~1,000

입력으로 주어지는 순서로 곱하려는 상황이고,

i번째 행렬의 열의 개수와

i+1번째 행렬의 행의 개수는 같다.

Output

* Line 1 : 필요한 곱셈의 최소 회수

Sample Input

Sample Output

Source

JAVA2015 PE8.6