셀룰러 네트워크

셀룰러 네트워크는 여러 개의 셀로 이루어진 무선 네트워크이며, 각 셀은 그 셀 안에 있는 기지국이 담당한다. 기지국은 자신이 담당하는 셀 안의 이동 단말(모바일)로부터 오는 호(call) 신호를 받아 유선 전화망에 연결한다. 어떤 모바일에게 걸려 온 호를 연결하려면, 네트워크는 그 모바일이 지금 어느 셀에 있는지 알아야 올바른 기지국으로 호를 전달할 수 있다.

모바일은 셀 사이를 이동한다. 만약 모바일이 셀 경계를 넘을 때마다 자신의 새 위치를 보고한다면 네트워크는 항상 정확한 셀을 알 수 있고, 모바일을 찾는 일(페이징)은 아주 간단해진다. 그러나 무선 대역폭 같은 자원이 부족하기 때문에 셀을 옮길 때마다 위치를 보고하는 것은 보통 현실적이지 않다. 그래서 호가 도착하는 시점에 네트워크는 모바일이 있을 수 있는 셀들을 제한된 범위로만 알고 있으며, 이 상황에서 모바일을 효율적으로 찾기 위해 여러 페이징 전략이 사용된다. 페이징 전략의 목표는 모바일을 찾을 때까지 걸리는 지연과 비용을 함께 최소화하는 것이다.

문제를 형식적으로 정의하자. 위치 구역(location area)은 $n$개의 셀로 이루어진 집합 $C = \{c_1, c_2, \dots, c_n\}$이며, 호가 도착하는 순간 모바일은 이 셀들 중 정확히 하나에 있다. 한 번의 페이징 라운드(한 단위 시간)에 네트워크는 이 셀들의 임의의 부분집합을 동시에 페이징하여, 모바일이 그 안에 있는지 여부를 알아낼 수 있다. 첫 라운드에 $n$개의 셀을 모두 페이징하는 것이 가장 빠르지만 무선 대역폭을 많이 소모한다.

많은 경우 네트워크는 모바일의 대략적인 위치를 알고 있고, 이를 $n$개의 독립적인 확률로 모델링할 수 있다. 셀 $c_i$에 모바일이 있을 확률을 $p_i$라 하자. 순차 페이징 전략은 셀들을 한 라운드에 하나씩 순서대로 페이징하고 모바일을 찾는 즉시 멈춘다. 이때 평균 페이징 비용(페이징한 셀의 수) $\bar{C}$와 평균 페이징 지연(라운드 수) $\bar{D}$는 다음과 같다.

$\bar{C} = \sum_{i=1}^{n} (i \times p_i), \qquad \bar{D} = \sum_{i=1}^{n} (i \times p_i).$

병렬 페이징 전략은 여러 셀을 동시에 페이징한다. 순차 페이징은 병렬 페이징보다 비용은 낮지만 지연은 크다. 병렬 페이징은 위치 구역의 셀들을 순서가 있는 여러 그룹, 즉 페이징 존(paging zone)으로 나눈다. $Z_1, Z_2, \dots, Z_w$를 $C$를 $w$개의 공집합이 아닌 존으로 나눈 분할이라 하자. 호가 도착하면 첫 라운드에 $Z_1$의 모든 셀을 동시에 페이징하고, 모바일을 찾지 못하면 다음 라운드에 $Z_2$의 모든 셀을 페이징하는 식으로 진행한다. 존 $Z_i$의 셀 수를 $n_i = |Z_i|$, 존 확률을 $\pi_i = \sum_{c_j \in Z_i} p_j$라 하면 다음이 성립한다.

$\bar{C} = \sum_{i=1}^{w} \left(\sum_{j=1}^{i} n_j\right) \pi_i, \qquad \bar{D} = \sum_{i=1}^{w} (i \times \pi_i).$

병렬 페이징에는 대역폭과 시간 사이의 트레이드오프가 있다. 존의 수를 늘리면 비용이 줄어드는 경향이 있고, 존의 수를 줄이면 비용이 커지는 경향이 있다. 또한 존의 수 $w$가 고정되어 있어도, 셀을 어떻게 나누는지에 따라 비용이 달라진다.

예를 들어 $n = 5$개의 셀이 있고 각 셀의 확률이 다음과 같다고 하자.

$Z_1 = \{c_1, c_2, c_3\}$, $Z_2 = \{c_4, c_5\}$로 나누면 다음과 같다.

• $\bar{C} = n_1\pi_1 + (n_1 + n_2)\pi_2 = 3(0.3 + 0.05 + 0.1) + (3 + 2)(0.3 + 0.25) = 3 \times 0.45 + 5 \times 0.55 = 4.1$
• $\bar{D} = 1 \times \pi_1 + 2 \times \pi_2 = 1(0.45) + 2(0.55) = 1.55$

$Z_1 = \{c_1, c_4\}$, $Z_2 = \{c_2, c_3, c_5\}$로 나누면 다음과 같다.

• $\bar{C} = n_1\pi_1 + (n_1 + n_2)\pi_2 = 2(0.3 + 0.3) + (3 + 2)(0.05 + 0.1 + 0.25) = 2 \times 0.6 + 5 \times 0.4 = 3.2$
• $\bar{D} = 1 \times \pi_1 + 2 \times \pi_2 = 1(0.6) + 2(0.4) = 1.4$

셀의 개수, 각 셀의 확률, 그리고 고정된 페이징 존의 수 $w$가 주어질 때, 평균 페이징 비용 $\bar{C}$가 최소가 되도록 셀들을 $w$개의 존으로 나누는 프로그램을 작성하라.

입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 두 정수 $n$과 $w$가 주어지는데, $n$은 위치 구역의 셀 수, $w$는 페이징 존의 수이며 $1 \le w \le n \le 100$이다. 둘째 줄에는 $n$개의 정수 $u_1, u_2, \dots, u_n$이 주어지며, 셀 $c_i$의 확률은 $p_i = u_i / (u_1 + u_2 + \dots + u_n)$이다. 모든 $u_i$는 1 이상 10000 이하이다.

각 테스트 케이스마다 모바일의 위치를 찾는 데 드는 최소 평균 페이징 비용을 소수점 아래 정확히 4자리로 반올림하여(반올림, round half up) 한 줄에 출력한다.