7235 : 카드 정렬
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 카드 묶음을 하나로 합치려 합니다. 두 묶음을 합칠 때 드는 비용은 두 묶음의 카드 수의 합과 같습니다.
총 비용을 최소화하는 방법으로 모든 카드 묶음을 합칠 때의 최소 비용을 구하십시오.
이 문제는 최소 힙(Heap)을 활용하는 그리디 알고리즘으로 최적해를 구할 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
총 비용을 최소화하는 방법으로 모든 카드 묶음을 합칠 때의 최소 비용을 구하십시오.
이 문제는 최소 힙(Heap)을 활용하는 그리디 알고리즘으로 최적해를 구할 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 $N$이 주어집니다. ($1 \le N \le 100{,}000$)
이어서 $N$개의 줄에 각 카드 묶음의 크기가 주어집니다.
이어서 $N$개의 줄에 각 카드 묶음의 크기가 주어집니다.
출력 설명
최소한의 비용으로 모든 카드 묶음을 하나로 합칠 때의 총 비용을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
10
20
30
40
출력 예시
COPY
복사되었습니다!
복사되었습니다!
190도움
매 단계에서 가장 작은 두 묶음을 합치면 최적입니다. Python의
heapq를 사용하여 최소 힙을 구현하십시오. $N=1$인 경우 비용은 0입니다.