밧줄 합치기 비용
실버 III의견: 0
길이가 각각 주어진 밧줄 \(N\)개를 모두 하나로 합치려 한다. 두 밧줄을 합칠 때 드는 비용은 두 밧줄의 길이의 합과 같고, 합친 결과는 그 길이를 가진 하나의 밧줄이 된다. 이 새 밧줄을 다시 다른 밧줄과 합칠 수 있다.
모든 밧줄을 하나로 합칠 때 드는 비용의 최솟값을 출력하여라. 밧줄이 하나뿐이면 합칠 필요가 없어 비용은 \(0\)이다.
\(1 \le N \le 100\,000\), 각 밧줄의 길이는 \(1\) 이상 \(1\,000\) 이하이다.
첫째 줄에 밧줄의 개수 \(N\)이 주어진다. 둘째 줄에 각 밧줄의 길이가 공백으로 구분되어 주어진다.
모든 밧줄을 하나로 합치는 데 드는 최소 비용을 출력한다.
3
1 2 3
9먼저 \(1\)과 \(2\)를 합쳐 비용 \(3\), 그 결과 \(3\)과 남은 \(3\)을 합쳐 비용 \(6\), 총 \(9\)이다. 가장 짧은 두 밧줄을 먼저 합치는 것이 최적이다.
1
5
0밧줄이 하나뿐이라 합칠 필요가 없다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
밧줄 합치기 비용
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
밧줄 합치기 비용