시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 293 | 125 | 110 | 55.276% |
크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.
예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×2인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.
같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.
행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.
첫째 줄에 행렬의 개수 N(2 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄부터 N+1번째 줄까지, i+1번째 줄에는 i번째 행렬의 크기 ri과 ci가 주어진다. (1 ≤ ri, ci ≤ 10,000)
항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.
주어지는 행렬의 크기는 단조감소함이 보장된다. 즉, 1 ≤ i < j ≤ n에 대해 ri ≥ rj, ci ≥ cj이다.
첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 263-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 263-1보다 작거나 같다.
3 5 3 3 2 2 2
42