배열에 숫자가 있습니다.

[1, 3, 5, 7, 9, 4, 8, 1, 2]

N개의 묶음으로 묶고 (연속되어야 함) 그 각각 묶음의 곱의 합 중 최소값을 구하는 알고리즘은 어떤 알고리즘을 적용해야 할까요?

예를들어 위의 배열에서 4묶음으로 나눌경우

1번 : [1, 3, 5] [ 7, 9] [4, 8 1] [2] 이고 각 묶음의 곱은 15 + 42 + 32 + 2 이고 합은 91이고

2번 : [1, 3] [5, 7, 9] [4, 8] [1 2]일 때 각 묶음의 곱은 3 + 255 + 32 + 2 = 282입니다.

따라서 1번과 같이 묶을 때 최소값이 됩니다.

어떤 알고리즘으로 접근해야 할지 몰라 문의 드립니다.