§ 1문제 정의
deliver()는 라이더를 src→dest로 자동 이동시키고 그만큼의 시간을 차감한다. 시간이 다 떨어지면 더는 배달할 수 없다. 가성비(점수/시간)가 좋은 배달부터 선택.
각 배달의 가성비 = (3,000 + 300d) / (라이더→src + d). 라이더 현재 위치에서 src가 가까울수록 ‘덤 거리’가 줄어 가성비 증가. 거리 d가 클수록 점수가 비례 증가하지만, 시간도 그만큼 빠진다.
실용적 풀이: 매번 가장 가까운 음식점의 가장 멀리 가는(=점수 큰) 배달부터 선택하면, 평균 가성비가 안정적으로 높다. 라이더 위치를 추적하면서 NN을 반복.
‘싸고 빠른 배달’이 답이 아니다. ‘덤 거리 적은 비싼 배달’이 답이다.
§ 2예제 시각화 — 3 음식점, 8 배달
FIG. 14 — pick best ratio, deliver, repeat
STEP 01 / 7
SPACE play/pause · ← → step · R reset
§ 3알고리즘 골격
process(rider, deliveries):
while time < LIMIT:
best = null
for d in remaining:
move = |rider - d.src|
dist = |d.src - d.dest|
if time + move + dist > LIMIT: continue
ratio = (3000 + 300*dist) / (move + dist)
if best == null or ratio > best.ratio:
best = d, best.ratio = ratio
if best == null: break
deliver(best.id)
rider = best.dest
time += move + dist