막대 사탕 합치기
플래티넘 I의견: 0
일렬로 놓인 \(N\)개의 사탕 더미가 있다. \(i\)번째 더미에는 사탕이 \(w_i\)개 들어 있다.
한 번의 연산으로 인접한 두 더미를 골라 하나로 합칠 수 있다. 두 더미를 합치는 데 드는 비용은 두 더미의 사탕 개수의 합이며, 합친 결과는 그 위치에 놓인 하나의 더미가 되어 사탕 개수는 두 더미의 합과 같다. 합쳐진 더미는 이후 다시 인접한 더미와 합칠 수 있다.
모든 더미를 하나로 합칠 때까지 드는 비용의 총합을 최소로 하려고 한다. 그 최솟값을 구하여라.
\(1 \le N \le 5{,}000\)
\(1 \le w_i \le 10^6\)
첫 줄에 더미의 수 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(w_1, \dots, w_N\)이 공백으로 구분되어 주어진다.
모든 더미를 하나로 합치는 데 드는 최소 비용을 한 줄에 출력한다.
4
10 20 30 40
190\([10,20,30,40]\). 먼저 \(10,20\)을 합쳐 \(30\)(비용 30), 그 결과와 \(30\)을 합쳐 \(60\)(비용 60), 마지막으로 \(60\)과 \(40\)을 합쳐 \(100\)(비용 100). 총 \(30+60+100=190\)이 최소이다.
1
99
0더미가 하나뿐이므로 합칠 필요가 없어 비용은 \(0\)이다.
riseoj 작성
출처 Original
평가 및 의견
막대 사탕 합치기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
막대 사탕 합치기