행렬 곱셈 순서 정하기
레벨 M1 · 코딩 · JavaScript · 목표 시간 17분 · 게시일 2026-10-23
행렬 n개를 차례로 곱한다. i번 행렬의 크기는 dims[i] × dims[i+1]이다(dims의 길이는 n+1). a × b 행렬과 b × c 행렬을 곱하면 곱셈이 a·b·c번 필요하다. 곱하는 순서(괄호 묶는 법)를 잘 정했을 때 필요한 곱셈 횟수의 최솟값을 구하시오. 행렬이 하나이면 0이다.
n은 1 이상 200 이하, dims의 각 값은 1 이상 100 이하이다. 모든 괄호 묶음을 따지는 방법으로는 시간 안에 끝나지 않는다.
예제
solve([10,30,5,60]) solve([40,20,30,10,30]) solve([7,3])