§ 1문제 정의
UE는 거의 정지해 있지만 20%는 매 분 한 칸 움직인다. 한 sub-task에서 5분이 흐른다. 그러므로 안테나의 반경은 “현재 거리”가 아니라 “5분 후까지의 최대 거리”다.
좋은 풀이의 발상: 각 UE에 대해 가장 가까운 10개 안테나까지의 거리 제곱합을 우선순위로 두고 정렬한다. 외진 UE부터 처리해서, 그들의 가장 가까운 안테나를 먼저 점유한다.
두 번째 sub-task에서 UE의 이동 방향이 드러나므로(5칸 이동 여부) 그 정보를 사용해 5칸 미래 위치까지 포함한 최대 반경을 산출한다. 이게 안테나 반경 제곱 합을 크게 줄인다.
정렬은 위치가 아닌 ‘외로움’으로 한다 — 가장 후미진 UE가 가장 먼저 자리를 차지한다.
§ 2예제 시각화 — 6개 안테나, 60개 UE
실제 100×100 평면을 60×40으로 줄였습니다. 검은 사각형이 안테나, 점이 UE. 붉은 원이 가동 반경. 외진 UE부터 잡으면 반경이 작아집니다.
FIG. 2 — capacity-aware antenna binding
STEP 01 / 6
SPACE play/pause · ← → step · R reset
§ 3알고리즘 골격
scanUE(UE_list, range[], connect[]):
sort UEs by Σ dist² to 10 nearest antennas # 외진 UE 먼저
for ue in sorted:
for antenna in (closest → farthest):
if antenna.capacity < 100:
antenna.capacity++
connect[ue] = antenna
range[a] = max(range[a], dist + future_move)
break
# sub-task 2 부터: 이동방향 dir[ue] 알려짐
# range 갱신 시 5칸 이동 후 좌표까지 포함