R01376
돌 합치기
골드 III레이팅
의견: 0
설명
일렬로 \(N\)개의 돌 더미가 놓여 있다. \(i\)번째 더미에는 \(a_i\)개의 돌이 있다.
석공은 인접한 두 더미를 골라 하나로 합칠 수 있다. 이때 합치는 비용은 두 더미의 돌 수의 합이다. 석공은 \(N - 1\)번의 합침을 반복하여 모든 돌을 하나의 더미로 만들어야 한다.
합치는 순서를 잘 선택하여 총 비용의 최솟값을 구하여라.
제약
- \(2 \le N \le 500\)
- \(1 \le a_i \le 10^6\)
입력 형식
첫째 줄에 더미의 수 \(N\)이 주어진다.
둘째 줄에 각 더미의 돌 수 \(a_1, a_2, \dots, a_N\)이 공백으로 구분되어 주어진다.
출력 형식
총 비용의 최솟값을 출력한다.
예제 1
입력
4
4 3 2 5
출력
28
설명
최적 순서: \((3, 2)\)를 합쳐 비용 \(5\), \((4, 5)\)를 합쳐 비용 \(9\), \((9, 5)\)를 합쳐 비용 \(14\). 합계 \(28\)이 최솟값이다.
예제 2
입력
4
1 1 1 1
출력
8
설명
네 돌을 최적으로 합치면 비용 합계는 \(8\)이다. 예를 들어 \((1,1) \to 2\), \((1,1) \to 2\), \((2,2) \to 4\)이면 \(2 + 2 + 4 = 8\)이다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
돌 합치기
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
돌 합치기
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기