§ 1문제 정의
평균 거리를 줄여봤자 의미가 없다. 가장 많이 달린 택시 하나가 채점된다. 풀이는 두 단계 — 그리디 NN 배정으로 시작, 그다음 균형 잡힌 swap.
1단계 NN: 매번 가장 적게 달린 택시를 골라, 가장 가까운 미할당 승객을 태운다. 일견 균형 잡힌 분배지만, 마지막에 남은 외진 승객이 한 택시의 점수를 폭증시킨다.
2단계 Swap: 가장 비싼 택시에서 한 승객을 떼어 가장 싼 택시의 적절한 위치에 끼워 넣는다. 이때 양쪽 모두 비용이 ‘현재 최댓값’ 아래로 유지되어야 한다. 500번 swap이면 충분.
평형은 정답이 아니다. 천장을 낮추는 것이 정답이다.
§ 2예제 시각화 — 5택시, 12승객
FIG. 5 — NN assignment → balancing swap
STEP 01 / 6
SPACE play/pause · ← → step · R reset
§ 3알고리즘 골격
run(N, M, drivers[], K, pax[]):
while there are unassigned passengers:
t = taxi with smallest score
p = unassigned passenger closest to t.pos
assign p to t, update t.score, t.pos = p.arrival
# 균형 잡기 — 500번 swap
for it in range(500):
big = taxi with max score, small = taxi with min score
find (i,j): move passenger big[i] into small[j]
such that both new scores < big.score
if no valid (i,j): break
swap and update