문제

Huffman 나라의 문자는 N개의 문자로 이루어져 있다. 0과 1로 이루어진 이진 인코딩이 발달한 대한민국과는 달리, Huffman 나라에서는 0부터 K-1까지의 숫자로 이루어진 K진법 인코딩이 발달했다.

우리는 Huffman 나라의 언어를 K진법으로 인코딩하려 한다. 이 때 다음 조건을 만족해야 한다.

1. N개의 각 문자에 K진법 문자열을 하나씩 배정해야 한다.
2. 배정된 K진법 문자열들이 서로의 접두사(prefix)일 수 없다.

예를 들어 아래의 표는 !, @, #, + 4개의 문자를 3진법으로 올바르게 인코딩한 예이다.

4개의 문자 각각에 서로의 접두사가 아닌 3진법 문자열을 할당했음을 확인해 볼 수 있다. 반면,

은 !에 013을 배정해서 첫 번째 조건을 만족하지 않고,

은 +이 #의 접두사이기 때문에 두 번째 조건을 만족하지 않는다.

Huffman 나라 언어 문자열이 하나 주어졌을 때, 이 문자열을 K진법으로 인코딩한 결과를 가장 짧게 만들면 길이가 어떻게 될까?
예를 들어 !!!@@@@#####++++++ 과 같이 !가 3번, @가 4번, #가 5번, +가 6번 문자열에 나타났다면, 첫 번째 표에서 제시한 인코딩을 적용한 경우 총 길이는 54가 된다 (3*3+4*3+5*3+6*3=54).