배달기사는 원본 자료에 grader의 deliver() 함수와 Coordinates·Delivery 구조체가 공개돼 있으나 — process()는 빈 스텁이고 검증된 통과 코드가 없다. 따라서 이 페이지는 라인 단위 해부 대신, grader의 deliver()가 실제로 어떻게 시간과 점수를 누산하는지를 정밀하게 읽어 — 이 문제를 시간 예산 제약 아래의 점수 최대화, 곧 분수 배낭(fractional knapsack)에 가까운 구조로 정식화하고, "가성비 우선 탐욕 + NN 라우팅"이라는 베스트 해법을 설계하고 논증한다. 추측이 들어가는 곳은 "설계 제안"임을 명시한다.
대부분의 SW Expert 문제가 SCORE를 최소화하는 데 반해, 배달기사는 SCORE를 최대화한다 — SCORE ≥ 140,000,000이면 PASS. 그리고 grader의 deliver() 본문이 공개돼 있어, 우리는 점수와 시간이 어떻게 움직이는지를 추측 없이 읽어낼 수 있다. 해법 설계는 이 함수를 읽는 데서 출발한다.
100 × 100, 거리는 맨해튼(Coordinates::operator-). 음식점 10개, 배달 DELIVERY_COUNT = 2000개. TC 5개.deliver(id)는 호출 시 — 라이더를 먼저 배달의 출발지(src)로 이동시키고(current_time += |src − rider|), 그 다음 목적지(dest)로 이동시킨다(current_time += |dest − src|).current_time ≤ TIME_LIMIT일 때에만 SCORE += 3000 + 300·(dest − src).current_time > TIME_LIMIT이면 점수만 안 들어올 뿐, 그 배달은 "완료"로 소진된다.deliver()는 current_time > TIME_LIMIT인 상태로 진입하면 false를 반환하고 아무 일도 안 한다 — 즉 예산이 바닥나면 게임 종료.move)는 점수에 들어가지 않는다 — 시간만 먹는다.move = |src − rider| — 라이더를 출발지로 데려가는 데 드는 순수 시간 손실(점수 0). 배달 거리 d = |dest − src| — 시간을 먹지만 점수 300·d를 벌어주는 거리. 같은 시간 1단위라도 회송에 쓰면 0점, 배달에 쓰면 300점이다. 베스트 해법의 본질은 — 점수를 만들지 않는 회송 거리를 최소화하면서, 점수당 시간이 좋은 배달을 우선 소비하는 것이다.
이 통찰에서 베스트 해법이 세 부분으로 정해진다.
이 분해는 물류배송 № 03·로봇청소기 № 01이 보였던 "독립된 관심사 분리"의 정신을 따른다 — 어느 배달이 가치 있는가(가치 모델)와 어떤 순서로 도느냐(라우팅)를 떼어내 각각 공략한다.
이 문제의 추상 구조를 못박는다. 시간 예산 B = 100{,}000이라는 한정 자원이 있고, 각 배달 i는 시간 t_i를 소비하며 점수 v_i를 준다. 예산 안에서 점수 합을 최대화 — 이것은 배낭 문제(knapsack)다.
매 deliver() 성공 호출 후 다음이 성립한다: current_time은 결코 줄지 않으며, 라이더는 방금 배달의 dest에 있다.
deliver()는 current_time에 두 비음 거리(move와 d)를 더하기만 한다 — 시간은 한 방향으로만 흐른다. 따라서 한 번 current_time > TIME_LIMIT이 되면 이후 모든 deliver()는 false다. 이 단조성이 — "예산은 회복 불가능한 자원"이라는, 배낭 정식화의 전제를 보장한다.
모든 배달 항목 i의 시간 비용 t_i가 예산 B에 비해 충분히 작다면(t_i ≪ B), 가성비 ratio_i = v_i/t_i 내림차순으로 배달을 고르는 탐욕은 분수 배낭의 최적해에 임의로 가깝다.
분수 배낭의 고전 결과: 항목을 단위 무게당 가치(여기서는 시간당 점수 ratio) 내림차순으로 채우는 탐욕이 최적이다. 증명은 교환 논법이다 — 어떤 해가 가성비 r인 배달을 빼고 더 낮은 가성비 r' < r인 배달을 넣었다면, 같은 시간으로 r 배달을 (분수만큼) 더 채워 점수를 늘릴 수 있다. 따라서 가성비 내림차순이 깨진 해는 항상 개선 가능하다.
배달기사는 배달을 쪼갤 수 없는 0/1 배낭이지만 — 항목 수가 2000개로 많고 개별 t_i가 예산 B=100{,}000에 비해 작다(맵 100²에서 거리는 최대 약 200, t_i는 수백 단위). 항목이 잘게 쪼개진 0/1 배낭은 분수 배낭과 거의 같은 값을 내므로, 가성비 탐욕의 손실은 "예산 끝자락에서 못 채운 마지막 한 칸" 수준 — B에 비해 무시할 만하다.
move = |src_i − rider| 항은 라이더의 현재 위치에 의존한다. 한 배달을 마칠 때마다 라이더가 이동하므로 — 모든 배달의 가성비가 매 라운드 다시 바뀐다. 따라서 "처음에 가성비로 한 번 정렬하고 그 순서대로 소비"하는 정적 전략은 틀렸다. 가성비는 라이더가 움직일 때마다 재평가되어야 하며 — 이것이 §3에서 "매 라운드 최선의 배달을 다시 고르는" 동적 탐욕을 쓰는 이유다.
풀이 코드가 없으므로 전체 골격은 의사코드로, 가성비 선택의 핵심부만 C++로 스케치한다. 전략은 "매 라운드, 현재 라이더 위치 기준으로 가성비 최선의 — 그리고 시간 예산 안에 드는 — 배달을 고른다"이다.
// 베스트 해법 골격 — 동적 가성비 탐욕 + 시간 예산 가드
process(rider, deliveries):
time = 0
done = {}
while time < TIME_LIMIT:
best = null
for d in deliveries not in done:
move = |d.src - rider|
dist = |d.dest - d.src|
cost = move + dist
if time + cost > TIME_LIMIT: continue // 예산 초과 — 점수 0
value = 3000 + 300 * dist
ratio = value / cost // 시간당 점수
if best == null or ratio > best.ratio:
best = d
if best == null: break // 더 채울 배달 없음 → 종료
deliver(best.id) // grader가 time·SCORE 갱신
rider = best.dest
time += best.move + best.dist
핵심은 매 라운드 가성비 최선의 배달을 고르되 — 시간 초과 배달을 미리 걸러내는 것이다. deliver()는 시간이 초과돼도 배달을 "완료"로 소진하므로(§1), 점수 0짜리 배달을 호출하면 그 배달을 영영 날린다. 아래는 한 라운드의 선택 부분 C++ 스케치다. 설계 제안 — 가성비 정의는 grader 공식 그대로지만, 정렬을 매번 전부 도느냐 일부만 보느냐 등은 튜닝 영역이다.
// 한 라운드 — 현재 라이더 위치 기준 가성비 최선의 배달 선택int pickBest(Coordinates rider, int curTime, const Delivery dv[], const bool done[]) { int bestId = -1; double bestRatio = -1.0; for (int i = 0; i < DELIVERY_COUNT; ++i) { if (done[i]) continue; int move = manhattan(dv[i].src, rider); // 회송 — 점수 0 int dist = manhattan(dv[i].dest, dv[i].src); // 배달 — 점수 발생 int cost = move + dist; if (curTime + cost > TIME_LIMIT) continue; // 예산 초과 → 건너뜀 int value = 3000 + 300 * dist; double ratio = (double)value / cost; // 시간당 점수 if (ratio > bestRatio) { bestRatio = ratio; bestId = i; } } return bestId; // -1 이면 더 채울 배달 없음 → 종료}
move와 dist를 분리한 것이 §1 통찰의 직접 구현이다 — value는 dist에만 비례하고(move는 점수 0), cost는 둘의 합이다. curTime + cost > TIME_LIMIT 가드가 §3 함정의 방어선이다: deliver()는 시간 초과 배달도 "완료"로 소진하므로, 점수 0이 될 배달을 미리 걸러야 한다. 한 라운드가 O(2000), 라운드 수가 배달 수 이하이므로 한 TC가 최악 O(2000²) = 4×10⁶ — 5 TC를 합쳐도 2×10⁷으로 5초 제한 안에 넉넉하다.
PASS는 SCORE ≥ 140{,}000{,}000, 5 TC 합산이다 — TC당 2.8×10⁷. 한 배달의 점수는 3000 + 300d로, 100² 맵에서 평균 배달 거리 d̄ ≈ 60\text{–}70이면 한 배달당 약 2.1×10⁴\text{–}2.4×10⁴점. TC당 2.8×10⁷을 채우려면 약 1200\text{–}1300건을 시간 안에 배달해야 한다 — 2000건 중 60~65%다. 시간 예산 B=100{,}000을 배달당 평균 시간(move + d̄)으로 나눈 값이 이 건수를 웃돌아야 PASS가 가능하다. 즉 회송 시간(move)을 얼마나 줄이느냐가 PASS의 임계 변수다 — 회송이 평균 d̄만큼 든다면 배달 가능 건수가 절반으로 줄어 PASS가 위태롭다. §4의 NN 라우팅이 이 회송을 공략하는 이유다.
§2·§3의 가성비 탐욕은 강력하지만 한 가지 긴장을 안고 있다 — 가성비 최선의 배달이 멀리 있을 수 있다. 가성비가 높아도 move가 크면 회송 시간이 다른 배달의 기회를 잡아먹는다. 이 긴장의 핵심은 move, 곧 회송 거리이며 — 회송을 구조적으로 줄이는 것이 베스트 해법의 마지막 층이다.
결정적 사실: 모든 배달의 출발지(src)는 10개 음식점 중 하나다(grader init()이 src = restaurant_list[idx]로 정한다). 2000개 출발지가 단 10개 좌표로 군집되어 있다는 뜻이다. 라이더가 한 음식점에 도착하면 — 그 음식점에서 나가는 모든 배달은 move 추가 비용 없이(이미 그 자리) 소비할 수 있다.
라이더가 음식점 R로 한 번 회송하면 — 그 회송 비용 |R − rider|는 한 번만 발생한다. 이후 R에서 나가는 배달들을 연달아 처리하는 한, 다음 배달의 src는 항상 직전 배달의 dest거나 R 근처다.
즉 한 음식점의 배달 묶음을 모아 처리하면, 그 음식점으로의 회송 1회를 k개 배달이 나눠 부담한다 — 배달당 회송 비용이 |R−rider|/k로 분할상각된다. 매번 다른 음식점으로 튀어다니면 매 배달이 풀 회송 비용을 무는 것과 대조된다. 노후화된도로 № 12의 "초과 보수 amortization"과 같은 분할상각 구조다.
NN 라우팅과의 결합. 그렇다고 한 음식점의 배달을 끝까지 다 비우는 것이 항상 옳지는 않다 — 그 음식점에 가성비 낮은 배달만 남으면 다른 음식점의 좋은 배달을 놓친다. 실전 설계 제안은 두 신호의 혼합이다:
음식점 NN이 회송 구조를, 가성비 탐욕이 점수 효율을 담당하는 분업이다 — 교차로신호제어 № 07의 "그린 웨이브 + 탐욕"과 똑같은 패턴이다.
| 전략 | 예산 활용 | 점수 경향 | 구현 | 평가 |
|---|---|---|---|---|
| 가까운 배달 우선 (회송 최소만) | 높음 | 낮음 | 쉬움 | 건수는 많으나 짧은 배달만 골라 배달당 점수가 작다 |
| 긴 배달 우선 (점수 최대만) | 낮음 | 중간 | 쉬움 | 배달당 점수는 크나 시간을 빨리 소진 — 건수가 적다 |
| 전역 최적 (0/1 배낭 + TSP) | 최대 | 최대 | 불가 | 회송이 라이더 경로에 의존 — 동적 TSP 결합은 5초 안에 못 푼다 |
| 동적 가성비 탐욕 + 음식점 NN | 높음 | 높음 | 중간 | 분수 배낭 탐욕(점수 효율) + NN(회송 분할상각)의 분업 |
표는 설계 비교다 — 측정된 점수가 아니라 각 전략이 SCORE에 어떻게 작용하는지를 정리한다. "가까운 배달 우선"은 회송을 최소화해 건수는 많지만 — 짧은 배달만 골라 배달당 점수(3000+300d의 d)가 작아 총점이 낮다. "긴 배달 우선"은 그 반대로, 배달당 점수는 크나 시간을 빨리 태워 건수가 줄고 예산을 비효율적으로 쓴다. 두 극단 모두 — 시간당 점수, 곧 가성비를 보지 않은 데서 실패한다. 전역 최적(0/1 배낭 + TSP)은 이론적 최대를 주지만, 회송 비용이 라이더의 방문 순서에 의존하는 동적 TSP와 배낭이 얽혀 5초 시간 제한 안에서 불가능하다. 따라서 — §2 Theorem 1(분수 배낭 탐욕의 근사 최적성)과 §4 Invariant(회송 분할상각)를 결합한 "동적 가성비 탐욕 + 음식점 NN"이 PASS 기준선(Theorem 2)을 넘길 가장 현실적인 후보다.
deliver()는 current_time > TIME_LIMIT이 돼도 — 점수만 안 줄 뿐 그 배달을 "완료"로 소진하고 라이더를 옮긴다. 예산 가드(curTime + cost ≤ TIME_LIMIT) 없이 호출하면, 점수 0짜리에 배달 하나와 시간을 모두 날린다.
3000 + 300·(dest − src) — 배달 거리에만 비례한다. 라이더→src 회송 거리는 시간만 먹고 점수는 0이다. 가성비 분자에 회송 거리를 잘못 넣으면 — 멀리 있는 배달을 과대평가한다.
move = |src − rider|는 라이더 위치에 의존하므로, 배달 하나를 마칠 때마다 모든 가성비가 바뀐다(§2 함정). 처음에 한 번 정렬한 순서를 끝까지 쓰면 회송이 폭증한다 — 매 라운드 재평가하라.
init())을 무시하고 매번 다른 음식점으로 튀면 — 회송 1회를 여러 배달이 나눠 부담하는 분할상각 이득을 통째로 버린다. PASS 기준선(Theorem 2)이 위태로워진다.
01번과 달리 이 페이지는 측정된 SCORE를 제시할 수 없다 — process()가 빈 스텁이고 검증된 통과 코드가 없기 때문이다. 다만 배달기사는 grader가 deliver() 본문을 공개하므로 검증 기반이 단단하다: 시간·점수 누산 규칙은 추측이 아니라 grader 코드에서 직접 도출된 사실이다. 정직한 검증 기준은 — 설계가 grader의 확정 제약(시간 단조성·예산 가드·점수 공식)과 모순되지 않는가, 그리고 PASS 기준선 분석(Theorem 2)이 일관적인가이다.
deliver()의 시간·점수 누산 규칙으로부터 베스트 해법을 설계하고 그 정당성을 논증한 것이다. "동적 가성비 탐욕 + 음식점 NN 라우팅"이라는 골격은 grader 코드에서 직접 연역된 가치 모델(§2)과 출발지 군집 구조(§4) 위에 서 있고, 음식점 소진 경계 같은 구체 수치만이 SCORE 측정을 요구하는 설계 제안이다. 이 페이지의 가치는 정답 코드가 아니라 — "시간 예산 제약 아래의 점수 최대화를, 어떻게 분수 배낭으로 정식화하고 가성비 탐욕으로 공략하는가"라는 사고의 골격에 있다.