허프만의 욕심

트리에 관한 기본 용어부터 정의한다. 트리는 다음과 같이 귀납적으로 정의된다. 트리에는 루트가 있으며, 루트는 외부 노드(잎, leaf)이거나, 자식으로 여러 개의 트리를 갖는 내부 노드이다. 내부 노드는 자기 자식 트리들의 루트에 대한 부모라고 부른다. 노드의 레벨(level) 도 귀납적으로 정의된다. 루트의 레벨은 $0$이고, 다른 노드의 레벨은 그 부모의 레벨보다 $1$ 크다.

이진 트리에서는 모든 내부 노드가 정확히 두 개의 자식, 즉 왼쪽 서브트리와 오른쪽 서브트리를 갖는다. 레이블이 붙은 이진 트리에서는 각 내부 노드가 문자열인 레이블을 추가로 갖는다. 이진 탐색 트리는 모든 내부 노드 $t$가 다음 조건을 만족하는, 레이블이 붙은 이진 트리이다. $t$의 왼쪽 서브트리에 있는 모든 레이블은 $t$의 레이블보다 작고, $t$의 레이블은 다시 오른쪽 서브트리에 있는 모든 레이블보다 작다. 비교는 문자열에 대한 사전식(알파벳) 순서를 사용한다.

중위 순회(inorder traversal) 는 잎을 만나면 그 잎을 방문하고, 내부 노드를 만나면 먼저 왼쪽 서브트리를 순회한 뒤 그 노드를 방문하고 마지막으로 오른쪽 서브트리를 순회한다. 따라서 이진 탐색 트리를 중위 순회하면 레이블이 사전식 순서대로 나열된다. 모양이 다른 이진 탐색 트리라도 중위 순회 결과는 같을 수 있다.

문자열 $s$를 찾을 때는 현재 루트의 레이블 $l$과 $s$를 비교한다. $s = l$이면 탐색을 끝내고, $s < l$이면 왼쪽 서브트리에서, $s > l$이면 오른쪽 서브트리에서 계속 찾는다. 잎에 도달하면 $s$가 트리에 없다는 뜻이다.

비교 횟수는 $s$와 트리의 모양에 따라 달라진다. 그러므로 주어진 문자열들을 저장하면서도 가능한 한 빠르게 접근할 수 있는 트리를 만들고자 한다. 어떤 문자열이 검색될지 미리 알 수 없으므로 확률 분포를 가정한다.

저장할 문자열의 개수를 $n$이라 하고, 이 문자열들을 사전식 순서로 $K_1, \dots, K_n$이라 하자. $p_1, \dots, p_n$과 $q_0, \dots, q_n$은 다음을 만족하는 $2n+1$개의 음이 아닌 실수이다.

$$\sum_{i=1}^{n} p_i + \sum_{i=0}^{n} q_i = 1.$$

이들의 의미는 다음과 같다.

• $p_i$ = 검색 문자열 $s$가 $K_i$와 같을 확률.
• $q_i$ = $s$가 사전식으로 $K_i$와 $K_{i+1}$ 사이에 엄격히 놓일 확률.

관례상 $q_0$은 $s < K_1$일 확률이고, $q_n$은 $s > K_n$일 확률이다.

레이블 $K_1, \dots, K_n$을 담으면서 기대 비교 횟수를 최소화하는 이진 탐색 트리를 찾고자 한다. 그 값은 다음과 같다.

$$\mathrm{cost} = \sum_{i=1}^{n} p_i \cdot \big(1 + \operatorname{level}(K_i)\big) + \sum_{i=0}^{n} q_i \cdot \operatorname{level}(\ell_i),$$

여기서 $\ell_i$는 $K_i$와 $K_{i+1}$ 사이에 엄격히 놓이는 문자열을 찾을 때 도달하는 잎이며, 경계의 경우는 위의 관례를 따른다.

예를 들어 $n = 2$이면 가능한 이진 탐색 트리의 모양은 정확히 두 가지이고, 정답은 그중 기대 비용이 더 작은 트리이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 $n$으로 시작하며 $1 \le n \le 200$이다. 이어서 $2n+1$개의 음이 아닌 정수, 즉 빈도(frequency)가 주어진다. 이 빈도들의 합을 $s$라 하면 $1 \le s \le 1,000,000$이다. 확률 $p_1, \dots, p_n$과 $q_0, \dots, q_n$은 이 순서대로 각 빈도를 $s$로 나누어 얻는다. 즉 처음 $n$개의 빈도가 $p_1, \dots, p_n$이고, 그다음 $n+1$개의 빈도가 $q_0, \dots, q_n$이다. 마지막 테스트 케이스 다음에는 $0$ 하나가 주어진다.

각 테스트 케이스에 대해, 주어진 빈도에 대한 어떤 이진 탐색 트리로도 달성할 수 있는 최소 기대 비교 횟수를 $\mathrm{cost}$라 할 때, 정수 $\mathrm{cost} \cdot s$를 한 줄에 출력한다.