이 페이지는 "왜 한 번에 적게 싣는 것이 이득인가"를 끝까지 따진다. 비용 함수 거리·(100 + 적재량·10)가 적재량에 선형이라는 사실에서 출발해, 배송지 사전할당의 정당성, 최근접 이웃(NN) 그리디의 근사 보증, 그리고 TH 파라미터가 50→30→20으로 작아질수록 점수가 11.36B→9.74B→9.35B로 떨어지는 트레이드오프의 수학을 PASS CUT 13B 위에서 해부한다.
물류배송 문제의 점수는 트럭이 움직인 모든 구간에서 거리 × (100 + 적재량 × 10)의 합이다. 100만 개 배송지에 정확한 물품을 모두 배달해야 하고(미배달 시 PENALTY 1조), 점수는 "트럭의 총 이동 비용을 얼마나 줄였는가"다.
비용 함수의 형태가 모든 설계를 지배한다. 이동 비용은 거리에 비례하되, 계수가 100 + 적재량·10이다 — 빈 트럭은 거리당 100, 50개를 가득 실은 트럭은 거리당 600. 즉 트럭은 무겁게 실을수록 같은 거리를 6배 비싸게 달린다. 이 한 가지 사실이 "한 번에 얼마나 실을 것인가(TH)"라는 핵심 파라미터를 만든다.
풀이는 세 단계로 분해된다.
sendCenterList에서 부품별 센터 목록 centerByProd와 센터별 부품수 행렬 prodCntByCenter를 구축한다. "어떤 물품을 어느 센터에서 구할 수 있는가"를 O(1)에 조회할 자료구조다.sendDeliveryList에서 100만 개 배송지 각각을, 그 배송지가 원하는 물품을 보유한 센터 중 가장 가까운 센터에 미리 할당한다. 센터별 배송지 목록 deliByCenter가 만들어진다.알고리즘의 골격(센터→픽업→배송)은 고정이다. 풀이의 지능은 단 하나의 상수 TH — 한 번의 센터 왕복에서 싣는 물품 개수 — 에 응축돼 있다. TH가 크면 센터를 덜 자주 들르지만 트럭이 무거운 채로 멀리 달린다. TH가 작으면 트럭은 가볍게 달리지만 센터 왕복이 잦아진다. 자료의 SCORE 기록 — TH=50: 11.36B, TH=30: 9.74B, TH=20: 9.35B — 은 이 줄다리기에서 가벼움이 이긴다는 것을 보여준다. 채택된 구현은 constexpr int TH = 20이다.
먼저 가장 강한 제약을 확인한다: 이 풀이는 반드시 100만 개 배송을 전부 완료하는가? run()은 solve() 후 delivery_order_list[i] >= 0인 배송지가 하나라도 남으면 false를 반환하고 PENALTY 1조가 부과된다.
채점기 main.cpp는 각 배송지의 물품이 어떤 센터엔가 반드시 재고로 존재하도록 데이터를 생성한다 — 배송지 물품 id를 뽑을 때 while (product_stock_count[id] == 0)로 재고 0인 물품을 거른다. 동시에 배송지를 만들 때마다 product_stock_count[id]--로 재고를 차감한다.
따라서 sub-task 시작 시점에 다음이 성립한다: 생성된 모든 배송 요청에 대해, 그 물품을 공급할 수 있는 센터 재고의 총합이 요청 수 이상이다. 사전할당은 이 불변식 위에서 동작한다.
sendDeliveryList의 사전할당은 모든 배송지를 정확히 하나의 센터에 배정하며, 각 (센터, 물품) 쌍의 배정 수가 그 센터의 재고를 초과하지 않는다. 그 결과 solve()의 픽업·배송 루프는 100만 개 배송을 모두 완료한다.
sendDeliveryList는 배송지 i를 처리할 때, 물품 pid를 가진 센터 목록 centerByProd[pid]를 훑어 가장 가까운 센터 cid를 고르고, 즉시 prodCntByCenter[cid][pid]--로 그 센터의 해당 물품 재고를 1 깎는다. 재고가 0이 되면 centerByProd[pid]에서 cid를 제거한다(목록 마지막 원소로 덮어쓰는 swap-delete).
이 동기화 덕분에, 한 번 0이 된 재고에는 다시 배송지가 배정되지 않는다 — 그 센터는 이미 후보 목록에서 빠졌다. Invariant가 "총 재고 ≥ 총 요청"을 보장하므로, 어떤 배송지도 "후보 센터가 모두 동남"인 상태를 만나지 않는다. 따라서 모든 배송지가 배정되고, solve()는 각 센터의 deliByCenter 목록을 빠짐없이 소진한다.
완전성이 보장되었으니 이제 점수다. 한 센터의 TH개 배송지를 방문하는 순서를 정하는 것은 작은 외판원 문제(TSP)다. 풀이는 getNearestDelivery로 매번 가장 가까운 미방문 배송지를 고르는 — 최근접 이웃(Nearest-Neighbor) 휴리스틱을 쓴다.
거리가 삼각부등식을 만족하는 metric TSP에서, 최근접 이웃 휴리스틱이 만드는 경로 길이는 최적 경로의 O(log n)배 이내다. 맨해튼 거리는 metric이므로 이 보증이 적용된다.
여기서 n = TH = 20으로 매우 작다. log 20 ≈ 3이지만, 이는 최악의 경우 상한이고 평균적으로 NN은 무작위 점 분포에서 최적의 25% 이내에 든다. TH가 작다는 사실이 NN의 약점(작은 클러스터 안에서만 근시안적)을 거의 무해하게 만든다.
각 배송지를 "가장 가까운 보유 센터"에 묶는 사전할당은, 트럭이 어떤 순서로 움직이든 피할 수 없는 최소 비용 — 센터에서 배송지까지의 직선 거리 — 을 가능한 한 작게 고정한다. 어떤 배송지를 더 먼 센터에 묶으면, 그 배송지를 거치는 모든 경로가 그 차이만큼 길어진다. 사전할당은 픽업·배송 순서 최적화(NN)와 독립적으로 비용 하한을 끌어내린다.
비용 모델을 형식적으로 적으면 다음과 같다. 트럭의 한 구간 이동 비용은 거리와 그 순간의 적재량으로 결정된다.
load는 트럭에 실린 물품 수다. 픽업 단계에서 load는 0→TH로 늘고, 배송 단계에서 TH→0으로 준다. 거리는 맨해튼 거리(operator-)이며 0~1998 범위다.
100만 배송지 각각에 대해 1천 센터를 전부 보지 않는다. 물품별 센터 목록 centerByProd[pid]를 미리 만들어 두면, 배송지가 원하는 물품을 가진 센터만 — seed=5에서 한 물품당 최대 16개 — 훑으면 된다. 100만 × 16 ≈ 1,600만 연산으로 끝난다.
void sendDeliveryList(int K, Coordinates deliveryCoordinatesList[], int deliveryProductList[]) { rnt i, j; for (i = 0; i < DLM; ++i) { // 1. 배송지 좌표·물품 백업 deli[i] = deliveryCoordinatesList[i]; prodByDeli[i] = deliveryProductList[i]; } for (i = 0; i < DLM; ++i) { // 2. 각 배송지를 최근접 보유센터에 할당 rnt cid = 0, minD = DLM; // 할당 센터, 최소 거리 rnt pid = prodByDeli[i]; // 이 배송지가 원하는 물품 rnt idx = 0; // centerByProd 안에서의 위치(삭제용) for (j = 0; j < centerLen[pid]; ++j) { // pid 보유 센터만 탐색 rnt tid = centerByProd[pid][j]; rnt tdist = deli[i] - center[tid]; // 맨해튼 거리 if (minD > tdist) { // 더 가까운 센터 발견 minD = tdist; cid = tid; idx = j; } } prodCntByCenter[cid][pid]--; // 그 센터의 pid 재고 1 차감 deliByCenter[cid][deliLen[cid]++] = i; // 센터별 배송지 목록에 추가 if (prodCntByCenter[cid][pid] == 0) { // 재고 소진 → 후보 목록에서 제거 centerByProd[pid][idx] = centerByProd[pid][--centerLen[pid]]; } }}
centerByProd[pid][idx] = centerByProd[pid][--centerLen[pid]] — 은 "마지막 원소로 덮어쓰고 길이를 줄이는" swap-delete다. 순서를 보존하지 않지만 O(1)이고, 후보 목록의 순서는 어차피 거리로 다시 평가되므로 무방하다. 이 한 줄이 §2 Proof의 핵심 — "재고 0인 센터는 두 번 다시 배정되지 않는다" — 를 강제한다. 재고 차감과 목록 삭제를 같은 반복 안에서 동기화하는 것이 완전 배송 보장의 토대다.
아래는 풀이의 심장부다. i += pcnt로 진행하므로 한 사이클이 끝날 때마다 처리한 배송 수만큼 전역 카운터가 전진한다.
void solve(Coordinates truckCoordinates) { truck = truckCoordinates; rnt i, j, pcnt; for (i = 0; i < DLM; i += pcnt) { // 100만 배송 소진까지 rnt cid = getNearestCenter(); // 배송 남은 가장 가까운 센터 truck = center[cid]; // 논리상 트럭을 센터로 pcnt = 0; for (j = 0; j < TH && deliLen[cid]; ++j) { // 최대 TH개 픽업 rnt idx = getNearestDelivery(deliByCenter[cid], deliLen[cid]); rnt id = deliByCenter[cid][idx]; // 최근접 배송지 truck = deli[id]; // 트럭을 그 배송지로(다음 NN 기준점) packs[pcnt] = id; // 방문 배송지 기록 prods[pcnt++] = prodByDeli[id]; // 대응 물품 번호 기록 deliByCenter[cid][idx] = deliByCenter[cid][--deliLen[cid]]; // 목록에서 제거 } truckLoading(cid, prods, pcnt); // 실제 채점기: 센터로 이동+적재 for (j = 0; j < pcnt; ++j) // 담긴 순서대로 배송 truckMove(packs[j]); }}
truck 변수의 두 의미에 주목하라. user 코드의 truck은 NN 계산을 위한 가상 위치일 뿐, 실제 점수는 채점기 main.cpp의 truck_pos로 누적된다. 픽업 루프에서 truck = deli[id]로 가상 위치를 갱신하는 것은 "다음 최근접 배송지를 직전 배송지 기준으로 찾기" — 즉 NN 체인을 잇기 위함이다. 실제 적재는 truckLoading(cid, ...) 한 번에 일어나고, 채점기는 그 시점에 truck_pos→센터 거리를 빈 트럭 요금(100)으로 청구한다. 배송은 truckMove가 packs[] 순서대로 호출하며, 매 구간이 점점 가벼워지는 트럭(TH→0)으로 청구된다.
사전할당: 10⁶ × centerLen ≈ 10⁶ × 16 = 1.6×10⁷. solve의 한 사이클: getNearestCenter가 O(1000), 픽업이 TH × deliLen — getNearestDelivery가 매번 남은 목록 전체를 훑으므로. 사이클 수는 10⁶ / TH. TH=20에서 사이클 수 5×10⁴, 사이클당 getNearestCenter 누적 5×10⁷. 픽업 비용은 센터별 목록 크기에 의존하나 한 센터의 목록은 한 번 시작하면 빠르게 소진된다. 전체적으로 ~10⁸ 규모 — O2에서 수 초 안에 끝난다.
이 풀이에서 유일하게 "조절 가능한" 것은 TH다. 자료에 기록된 세 측정값이 TH의 효과를 정량적으로 보여준다.
| TH | 측정 SCORE | CUT 대비 여유 | 해석 |
|---|---|---|---|
| 50 (만적재) | 11,365,038,530 | 12.6% | 센터 왕복 최소, 그러나 무거운 채로 멀리 달림 |
| 30 | 9,742,824,170 | 25.1% | 균형점에 근접 — 1.62B 개선 |
| 20 | 9,347,434,370 | 28.1% | 채택 — 가벼운 주행이 잦은 왕복을 이김 |
한 사이클의 비용을 두 항으로 나눠 보자. 왕복 항은 트럭이 (이전 위치 → 센터)로 빈 채(요금 100) 가는 거리다. 주행 항은 픽업·배송하며 움직이는 거리이며, 적재량에 따라 요금이 100~(100+TH·10) 사이를 오간다.
TH를 늘리면 왕복 횟수(10⁶/TH)가 줄어 빈 트럭 왕복 항이 절약된다. 그러나 동시에 한 사이클 안에서 트럭이 더 무거워지고, 픽업·배송의 모든 구간 요금이 올라간다. 측정값이 말하는 바는 분명하다 — TH 50→20으로 줄일 때 점수가 11.36B→9.35B로 2.01B(약 18%) 개선된다. 즉 이 데이터에서는 주행 요금 절감(가벼운 트럭)이 왕복 항 증가를 압도한다.
직관적 이유: 적재량 변동비 계수는 거리당 load·10이고, load는 최대 TH까지 간다. TH=50이면 무거운 구간의 요금이 100+500=600 — 빈 트럭의 6배다. 배송지가 1000×1000 맵에 흩어져 있어 구간 거리들이 짧지 않으므로, "비싼 요금 × 긴 거리"의 누적이 왕복 절감보다 크다. 반대로 왕복 항은 요금이 100으로 고정 — 가장 싼 요금이라, 왕복이 좀 늘어도 타격이 작다.
| 전략 | 완전성 | 점수 경향 | 구현 | 평가 |
|---|---|---|---|---|
| 입력 순서대로 배송 | 보장 | CUT 초과 | 쉬움 | 지리적 인접성 무시 — 트럭이 맵을 무작위로 횡단 |
| 만적재(TH=50) NN | 보장 | 11.36B | 중간 | 왕복은 최소지만 무거운 주행 요금이 점수를 끌어올림 |
| 전역 TSP 최적 경로 | 보장 | 이론 최소 | 불가 | 100만 점 TSP는 NP-난해 — 시간 안에 불가능 |
| 사전할당 + NN + TH=20 | 보장 | 9.35B | 중간 | 거리 1차최적화(사전할당) + 가벼운 주행 + 작은 NN |
표가 드러내는 구조는 명확하다. 완전성(Theorem 1)은 사전할당과 재고 동기화로 보장된다. 진짜 경쟁은 이동 비용에서 벌어지며, 두 개의 비용원 — 빈 트럭 왕복(고정비)과 적재 주행(변동비) — 을 동시에 공략해야 한다. 입력 순서 배송은 둘 다 방치하고, 만적재 NN은 왕복만 줄이다 주행 요금에서 손해 본다. 전역 TSP는 이론 최소를 주지만 100만 점에서 계산 불가능하다. 사전할당으로 거리 하한을 끌어내리고, 작은 TH로 주행을 가볍게 하고, 작은 NN으로 클러스터 내 순서를 다듬는 조합만이 CUT 13B를 28% 여유로 통과한다.
prodCntByCenter를 깎으면서 centerByProd에서 제거하는 두 동작이 같은 반복 안에서 동기화돼야 한다. 한쪽만 갱신하면, 재고 0인 센터에 배송지가 또 배정돼 — 픽업 시 그 물품이 없어 — 미배달이 발생하고 PENALTY 1조를 맞는다.
truck은 NN 계산용 가상 위치다. 실제 점수는 truckMove·truckLoading 호출 시점에 채점기 truck_pos 기준으로 청구된다. 둘을 혼동해 user truck으로 점수를 추정하면 빗나간다.
truckLoading은 listSize + truck_package_count > 50이면 0을 반환하고 적재 실패다. TH ≤ 50이어야 하며, 트럭이 직전 사이클을 다 비우고 시작하므로 TH=20은 안전하다. TH를 51 이상으로 잘못 잡으면 적재가 통째로 실패한다.
packs[55]·prods[55]는 TH(최대 50)보다 크게 잡혀 있다. TH를 56 이상으로 키우면 배열 범위를 벗어나 메모리가 깨진다 — TH 튜닝 시 배열 크기도 함께 봐야 한다.
getNearestCenter는 if (deliLen[i] == 0) continue;로 배송 남은 센터만 본다. 이 가드가 없으면 빈 센터가 최근접으로 뽑혀 픽업 루프가 0개를 픽업, pcnt=0이 되어 i += pcnt가 전진하지 못하고 무한 루프에 빠진다.
이 풀이가 "통과한다"는 주장의 근거는 추측이 아니라 채점기 출력과 자료에 기록된 SCORE 측정값이다. main.cpp는 seed=5로 데이터를 생성하고, truckMove·truckLoading 호출마다 거리·(100+적재량·10)을 SCORE에 누산한다. solve() 후 미배달 배송지가 하나라도 남으면 SCORE = PENALTY 1조다.
g++ -O2로 main.cpp + user.cpp를 컴파일하고 constexpr int TH = 20으로 두면 채점기가 SCORE: 9347434370 과 PASS를 출력한다. TH를 30·50으로 바꿔 다시 돌리면 자료에 기록된 9.74B·11.36B가 재현된다 — §4의 TH 튜닝 곡선이 측정으로 확인된다. 채점기가 점수를 직접 누산하므로 이 숫자는 풀이의 객관적 성적표다.