Funcia
Lv.3dpinterval-dp

행렬 곱셈 순서

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

행렬 n개를 차례로 곱하려고 합니다. i번째 행렬의 크기는 dims[i] × dims[i+1]입니다(dims의 길이는 n + 1).

크기가 p × q인 행렬과 q × r인 행렬을 곱하면 곱셈이 p × q × r번 필요합니다. 행렬 곱셈은 결합 법칙이 성립하므로 괄호를 치는 순서에 따라 전체 곱셈 횟수가 달라집니다. 순서는 바꿀 수 없습니다.

모든 행렬을 곱하는 데 필요한 곱셈 횟수의 최솟값을 반환하세요. 행렬이 하나면 0입니다.

입출력 예

dimsresult
[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

제한 사항

  • 2≤2 \le dims.length ≤201\le 201 (행렬은 최대 200개)
  • 1≤1 \le dims[i] ≤1,000\le 1{,}000
  • 답은 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이고, 구간 길이가 짧은 것부터 채워야 오른쪽 식의 값이 이미 준비돼 있습니다.

곱셈 횟수는 최대 200×109200 \times 10^9 정도라 64비트 정수를 쓰세요.

복잡도 목표

모든 괄호 배치를 메모 없이 재귀로 시도하면 경우의 수가 카탈랑 수만큼 늘어 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness406판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.