행렬 곱셈 순서
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
행렬 n개를 차례로 곱하려고 합니다. i번째 행렬의 크기는 dims[i] × dims[i+1]입니다(dims의 길이는 n + 1).
크기가 p × q인 행렬과 q × r인 행렬을 곱하면 곱셈이 p × q × r번 필요합니다. 행렬 곱셈은 결합 법칙이 성립하므로
괄호를 치는 순서에 따라 전체 곱셈 횟수가 달라집니다. 순서는 바꿀 수 없습니다.
모든 행렬을 곱하는 데 필요한 곱셈 횟수의 최솟값을 반환하세요. 행렬이 하나면 0입니다.
입출력 예
| dims | result |
|---|---|
[10, 30, 5, 60] | 4500 |
[40, 20, 30, 10, 30] | 26000 |
[7, 3] | 0 |
입출력 예 설명
예 1 — (A × B) × C는 10·30·5 + 10·5·60 = 4500, A × (B × C)는 30·5·60 + 10·30·60 = 27000입니다.
예 3 — 행렬이 하나뿐입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(dims: int[]) → long
제한 사항
-
dims.length(행렬은 최대 200개) -
dims[i] - 답은 32비트 정수를 넘을 수 있습니다.
기대 복잡도
- 시간
- O(N^3)
- 공간
- O(N^2)
입출력 예
| dims | 기대 출력 |
|---|---|
[10,30,5,60] | 4500 |
[40,20,30,10,30] | 26000 |
[7,3] | 0 |
힌트
힌트
구간 DP입니다. cost[i][j] = "i번부터 j번 행렬까지 곱하는 최소 횟수"로 두면, 마지막 곱셈이 어디서 나뉘는지(k)로 경우를 나눌 수 있습니다.
cost[i][j] = min over i ≤ k < j of ( cost[i][k] + cost[k+1][j] + dims[i] · dims[k+1] · dims[j+1] )
cost[i][i] = 0이고, 구간 길이가 짧은 것부터 채워야 오른쪽 식의 값이 이미 준비돼 있습니다.
곱셈 횟수는 최대 정도라 64비트 정수를 쓰세요.
복잡도 목표
모든 괄호 배치를 메모 없이 재귀로 시도하면 경우의 수가 카탈랑 수만큼 늘어 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 6 | 판정만 |
| performance | 60 | 4 | 판정만 |