| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 321 | 151 | 128 | 52.675% |
마리사는 바닥에 일렬로 늘어놓은 $N$장의 카드로 마법을 연습하고 있다. 왼쪽에서부터 $i$번째에 있는 $i$번 카드의 마력 소모량은 $a_i$로 표현된다. 마리사가 $i$번 카드에 마법을 사용하기 위해서는 $a_i$만큼의 마력을 소모해야 한다.
마리사는 인접한 두 카드를 골라서 마법을 시전한다. 이때 마리사는 고른 두 카드의 마력 소모량의 합만큼 마력을 소모한다. 이후 두 카드는 그 자리에서 하나로 합쳐지며, 새로 만들어진 카드의 마력 소모량은 이전 두 카드의 마력 소모량 중 최댓값이 된다. 이 과정은 카드가 단 하나만 남을 때까지 반복한다.
마리사는 소모하는 마력을 최소화하려 한다. 이때 마리사가 소모할 마력의 양을 구해주자!
첫 번째 줄에 카드의 개수 $N$이 주어진다. $(1 \leq N \leq 400)$
두 번째 줄에 카드의 마력 소모량을 나타내는 정수 $a_1, a_2, \cdots, a_N$가 공백으로 구분되어 주어진다. $(1 \leq a_i \leq 10^9)$
마리사가 소모하는 마력의 최솟값을 출력한다.
3 1 1 1
4
마리사가 $1$번 카드와 $2$번 카드를 합치며 $2$의 마력을 소모한다. 이후 카드는 $[1, 1]$이 된다.
마리사가 마지막 남은 두 카드를 합치며 $2$의 마력을 소모한다. 마력의 총 소모량은 $4$이며, 이보다 마력을 적게 소모하는 방법은 존재하지 않는다.
4 1 100 100 1
402
마리사가 $2$번 카드와 $3$번 카드를 합치며 $200$의 마력을 소모한다. 이후 카드는 $[1, 100, 1]$이 된다.
마리사가 앞의 두 카드를 합치며 $101$의 마력을 소모한다. 이후 카드는 $[100, 1]$이 된다.
마리사가 마지막 남은 두 카드를 합치며 $101$의 마력을 소모한다. 마력의 총 소모량은 $402$이며, 이보다 마력을 적게 소모하는 방법은 존재하지 않는다.
1 516
0
이미 카드가 한 장이므로, 마리사는 마법을 사용할 필요가 없다.
4 5 10 2 7
41
마리사가 $1$번 카드와 $2$번 카드를 합치며 $15$의 마력을 소모한다. 이후 카드는 $[10, 2, 7]$이 된다.
마리사가 뒤쪽의 두 카드를 합치며 $9$의 마력을 소모한다. 이후 카드는 $[10, 7]$이 된다.
마리사가 마지막 남은 두 카드를 합치며 $17$의 마력을 소모한다. 마력의 총 소모량은 $41$이며, 이보다 마력을 적게 소모하는 방법은 존재하지 않는다.