R00405
돌 무더기 합치기
플래티넘 III레이팅
의견: 0
설명
일렬로 놓인 \(N\)개의 돌 무더기가 있다. \(i\)번째 무더기에는 돌이 \(a_i\)개 있다.
인접한 두 무더기를 골라 하나로 합칠 수 있으며, 이때 두 무더기의 돌 개수 합만큼 비용이 든다. 모든 무더기를 하나로 합칠 때까지 반복할 때, 비용 합의 최솟값을 구하여라.
구간 동적 계획법의 단순한 \(O(N^3)\) 풀이는 통과할 수 없다. 최적 분할점의 단조성을 이용하는 최적화가 필요하다.
제약
\(1 \le N \le 4{,}000\)
\(1 \le a_i \le 10{,}000\)
입력 형식
첫 줄에 무더기의 수 \(N\)이 주어진다.
둘째 줄에 \(a_1, \dots, a_N\)이 주어진다.
출력 형식
비용 합의 최솟값을 한 줄에 출력한다.
예제 1
입력
4
40 30 30 50
출력
300설명
(30,30)을 합쳐 60(비용 60), (40,60)을 합쳐 100(비용 100), (100,50)을 합쳐 150(비용 150). 총 비용은 310으로 최소이다.
예제 2
입력
1
7
출력
0설명
무더기가 하나뿐이므로 합칠 필요가 없어 비용은 0이다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
돌 무더기 합치기
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
돌 무더기 합치기
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기