§ 1문제 정의
트럭은 원형 트랙을 시계/반시계로 임의의 거리만큼 이동할 수 있다. 비용은 적재 무게에 비례 — 무거울수록 멀리 가지 마라.
현재 위치에서 가까운 화물을 모은 뒤, 같은 방향에 목적지가 몰린 화물을 우선 적재한다. 적재 100을 채우는 것이 정답이 아닐 수도 있다 — 50 정도만 모아 빠르게 일주하는 편이 평균 비용을 낮춘다.
원형 구조의 이점: 거리 = min(d, 1000-d). 반대 방향으로 더 짧을 수 있으니, 경로 선택은 두 옵션을 모두 비교해야 한다.
원형 트랙에서 “정방향”은 없다. 매번 두 방향을 모두 재본다.
§ 2예제 시각화 — 8역, 6화물
FIG. 10 — load batch, choose direction, deliver clockwise
STEP 01 / 6
SPACE play/pause · ← → step · R reset
§ 3알고리즘 골격
process(cargos, cnt):
truck.pos = 0; truck.weight = 0
while any cargo remains:
# 1. 현재 위치에서 가까운 화물을 그리디로 적재
while truck.weight + smallestNearbyCargo <= 100:
move(±d to nearestStationWithCargo)
load(bestCargo)
# 2. 적재된 화물 중 목적지가 같은 방향에 몰린 그룹으로 배달
sort onboard by min(dist_cw, dist_ccw)
for cargo in sorted:
move(±d_min)
unload(cargo)