6067 : 최소 비용으로 합치기
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
최소 비용으로 합치기 (허프만)
N개의 묶음을 하나씩 두 묶음을 합쳐 최종적으로 하나의 묶음으로 만들려 합니다.
두 묶음을 합칠 때 드는 비용은 두 묶음의 크기의 합입니다.
우선순위 큐를 이용해 항상 가장 작은 두 묶음을 꺼내 합쳐 나가는 탐욕법(Greedy)으로 최소 총 비용을 구하시오.
예시: [1, 2, 3, 4]
- 1+2=3, 비용 3 → [3, 3, 4]
- 3+3=6, 비용 6 → [4, 6]
- 4+6=10, 비용 10 → [10]
- 총 비용 = 19
[제약 조건]
• 수의 개수 $N$: $1 \le N \le 100{,}000$ (정수)
• 각 수: $1 \le a_i \le 10^9$ (정수)
• 결과값이 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력합니다.
N개의 묶음을 하나씩 두 묶음을 합쳐 최종적으로 하나의 묶음으로 만들려 합니다.
두 묶음을 합칠 때 드는 비용은 두 묶음의 크기의 합입니다.
우선순위 큐를 이용해 항상 가장 작은 두 묶음을 꺼내 합쳐 나가는 탐욕법(Greedy)으로 최소 총 비용을 구하시오.
예시: [1, 2, 3, 4]
- 1+2=3, 비용 3 → [3, 3, 4]
- 3+3=6, 비용 6 → [4, 6]
- 4+6=10, 비용 10 → [10]
- 총 비용 = 19
[제약 조건]
• 수의 개수 $N$: $1 \le N \le 100{,}000$ (정수)
• 각 수: $1 \le a_i \le 10^9$ (정수)
• 결과값이 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력합니다.
입력 설명
첫째 줄에 묶음의 개수 N (1 ≤ N ≤ 10,000)이 주어집니다.
둘째 줄에는 각 묶음의 크기(정수) N개가 공백으로 구분되어 주어집니다.
둘째 줄에는 각 묶음의 크기(정수) N개가 공백으로 구분되어 주어집니다.
출력 설명
모든 묶음을 하나로 합치기 위해 필요한 최소 총 비용을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
1 2 3 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
19