영화 편집 작업에서 일렬로 놓인 \(N\) 개의 클립 파일을 하나로 합치려 합니다. \(i\) 번째 파일의 크기는 \(w_i\) 입니다.

한 번에 인접한 두 파일만 합칠 수 있고, 합치는 비용은 두 파일 크기의 합과 같습니다. 합쳐진 파일은 다시 하나의 파일이 되어 인접 관계가 유지됩니다.

모든 파일을 하나로 합칠 때 드는 총 비용의 최솟값을 구하세요.

\(1 \le N \le 400\), \(1 \le w_i \le 1000\)

첫 줄에 파일의 수 \(N\) 이 주어집니다. (\(1 \le N \le 400\))

둘째 줄에 \(N\) 개의 정수 \(w_1, \dots, w_N\) 이 주어집니다. (\(1 \le w_i \le 1000\))

모든 파일을 하나로 합치는 최소 총 비용을 출력합니다. \(N=1\) 이면 \(0\) 을 출력합니다.

riseoj 작성

출처 Original