8027 : 가변 진법 허프만
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 기호와 각 기호의 빈도수가 주어집니다. 우리는 $R$진법(Radix $R$) 허프만 코드를 구축하여 코드의 가중치 패스 길이(Weighted Path Length, 즉 각 기호의 빈도수와 코드 길이의 곱의 총합)를 최소화하고자 합니다.
최적의 $R$진 허프만 코드를 구축했을 때의 최소 가중치 패스 길이를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le T \le 50$ (테스트 케이스 수)
• $1 \le N \le 1,000$
• $2 \le R \le 10$
• $1 \le f_i \le 10^9$ (각 기호의 빈도수)
최적의 $R$진 허프만 코드를 구축했을 때의 최소 가중치 패스 길이를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le T \le 50$ (테스트 케이스 수)
• $1 \le N \le 1,000$
• $2 \le R \le 10$
• $1 \le f_i \le 10^9$ (각 기호의 빈도수)
입력 설명
첫째 줄에 테스트 케이스의 개수 $T$가 주어집니다.
각 테스트 케이스의 첫째 줄에는 기호의 개수 $N$과 진법 $R$이 공백으로 구분되어 주어집니다.
둘째 줄에는 $N$개의 정수로 각 기호의 빈도수 $f_1, f_2, \ldots, f_N$이 공백으로 구분되어 주어집니다.
각 테스트 케이스의 첫째 줄에는 기호의 개수 $N$과 진법 $R$이 공백으로 구분되어 주어집니다.
둘째 줄에는 $N$개의 정수로 각 기호의 빈도수 $f_1, f_2, \ldots, f_N$이 공백으로 구분되어 주어집니다.
출력 설명
각 테스트 케이스마다 최적 $R$진 허프만 코드의 최소 가중치 패스 길이를 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
1
4 3
2 3 5 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
22도움
$R$진 허프만 코딩에서는 매 단계마다 우선순위 큐에서 가장 빈도수가 작은 $R$개의 노드를 꺼내 합칩니다.
단, 노드들이 매번 정확히 $R$개씩 묶여 최종적으로 1개가 남도록 하기 위해, $(N-1) \pmod{R-1} \neq 0$인 경우 빈도수가 0인 더미(Dummy) 노드를 $(R-1) - ((N-1) \pmod{R-1})$개 추가한 후 알고리즘을 진행해야 합니다.
단, 노드들이 매번 정확히 $R$개씩 묶여 최종적으로 1개가 남도록 하기 위해, $(N-1) \pmod{R-1} \neq 0$인 경우 빈도수가 0인 더미(Dummy) 노드를 $(R-1) - ((N-1) \pmod{R-1})$개 추가한 후 알고리즘을 진행해야 합니다.