원형화물배치는 원본 자료에 grader만 공개돼 있고 검증된 통과 코드가 없다. 따라서 이 페이지는 — 라인 단위 코드 해부 대신, move/load/unload 비용 함수를 읽고 베스트 해법을 설계하며 정당성을 논증한다. 비용이 (weight+50)·(distance+10)인 까닭에 왜 "빈 열차로 멀리, 무거운 열차로 짧게"가 강제되는지, 원형 트랙의 시계/반시계 최단거리가 왜 핵심 metric인지, 적재용량 100이 어떻게 묶음(batch) 배송을 강제하는지를 설계 의사코드와 C++ 스케치로 제시한다. 추측이 들어가는 곳은 설계 제안으로 표시한다.
원형화물배치는 통과 코드가 없다. 그러나 채점기의 move/load/unload와 verify()가 완전히 공개돼 있고, 좋은 해법의 형태는 거기서 연역할 수 있다. 먼저 비용과 제약을 정확히 적는다.
비용 함수 (weight+50)·(distance+10)를 펼치면 두 가지 사실이 드러난다. 첫째, 무게와 거리가 곱으로 결합한다 — 무거운 열차가 먼 거리를 가면 비용이 폭증한다. 둘째, +50·+10 상수항 때문에 아무리 가볍고 짧아도 이동에는 최소 비용이 든다(빈 열차 1칸 = 50·11 = 550). 즉 이동 횟수 자체도 비용이다.
이 두 사실에서 베스트 해법의 골격이 곧바로 나온다.
weight가 곱해지므로, 짐을 많이 실은 구간은 거리를 최소화해야 한다. 빈 열차(weight 0)의 이동은 50만 곱해지므로 상대적으로 싸다 — 멀리 가야 한다면 빈 채로 가라.+10·+50 때문에 잦은 짧은 이동은 손해다. 적재용량 100이 허락하는 한 한 번 출발할 때 최대한 많이 싣고, 같은 방향 목적지들을 한 묶음으로 처리한다.그래서 베스트 해법은 두 단계로 설계된다.
핵심 통찰은 1단계가 "무엇을 같이 옮길까"(조합), 2단계가 "어떤 순서로 돌까"(경로)를 푸는 것이며, 둘 다 비용 함수의 두 원칙에 종속된다는 점이다.
(무게)×(거리) 곱 구조일 때, "무게"와 "거리"를 따로 줄이려 하지 마라 — 둘이 겹치는 구간을 줄여야 한다. 무거운 열차가 다니는 거리를 짧게, 긴 거리는 빈 열차로. 그리고 상수항이 이동 횟수에 비례하는 비용을 만들므로, 적재용량이 허락하는 한 한 번에 많이 실어 출발 횟수를 줄여라.
설계의 정당성을 논증하려면 먼저 가능성(feasibility)을 확인해야 한다. 점수보다 우선, verify()는 열차에 화물이 남아 있거나(train.num > 0) 화물이 제 목적지 역에 없으면 false를 반환해 PENALTY 10¹⁴를 부과한다.
설계의 모든 단계에서 다음이 성립해야 한다: 실은 화물은 정확히 그 목적지 역에서만 내려지고, process 종료 시 열차는 비어 있다(train.num == 0).
load는 train.weight + cargo.weight ≤ 100일 때만 성공하므로, 적재용량은 채점기가 강제한다 — 초과 적재는 load가 거부해 자동으로 막힌다. 그러나 "모든 화물을 결국 목적지에 내려놓기"는 채점기가 대신 해주지 않는다. 각 화물 id마다 load와 unload가 정확히 한 번씩 짝지어 호출되고, 마지막 화물까지 하역돼야 이 불변식이 지켜진다.
둘레 1000의 원형 트랙에서 위치 a에서 b로 가는 최소 이동 거리는 d(a,b) = min(\,(b−a) \bmod 1000,\; (a−b) \bmod 1000\,)이며, 그 최댓값은 500이다. 어떤 한 화물을 옮기든, 이 거리보다 짧게 갈 수는 없다 — 이것이 이동 비용의 하한이다.
원형 트랙에서 두 역을 잇는 경로는 정확히 두 개다 — 시계 방향 호와 반시계 방향 호. 두 호의 길이 합은 둘레 1000이다. 따라서 한 호가 k이면 다른 호는 1000−k이고, 더 짧은 쪽은 min(k, 1000−k) ≤ 500이다.
채점기 move(mDistance)는 부호 있는 거리를 받아 pos = (pos + mDistance + MAPSIZE) % MAPSIZE로 위치를 갱신하고, 비용에는 |mDistance|를 쓴다. 그러므로 mDistance로 짧은 호의 부호 있는 거리를 주면 정확히 최단거리 비용이 든다. 한 화물을 한 번에 옮긴다면 이보다 나은 방법이 없다.
흔한 오해: "한 화물씩 출발역→목적지로 곧장 나르면 각 화물이 최단거리를 타니 최적 아닌가?" — 아니다. 낱개 배송은 빈 열차로 되돌아오는 회송(deadhead)을 무시한다. 화물 하나를 목적지에 내린 뒤 다음 화물의 출발역으로 가려면 빈 열차가 또 이동해야 한다. 화물이 수천 개면 회송만으로 비용이 누적된다.
출발역들과 목적지역들이 트랙 위 같은 호(弧) 구간에 몰린 화물 묶음을 생각하자. 열차가 그 구간을 한 방향으로 한 번 훑으며 지나는 역마다 싣고 내리면, 회송이 따로 생기지 않는다 — 다음 화물의 출발역이 진행 방향 앞에 있으므로 "이동하다 들르기"가 된다.
낱개 배송의 회송 비용이 묶음 배송에서는 화물 운반 이동에 흡수된다. 비용 함수의 상수항 +50·+10이 이동 횟수에 비례하므로, 출발 횟수를 줄이는 묶음 배송은 그 상수 비용도 함께 줄인다. 적재용량 100은 이 묶음의 크기 상한이며 — 한 묶음 안에서 무게 합이 100을 넘지 않게 화물을 골라야 한다.
이 문제의 비용은 move 호출 때마다 누적된다. 한 화물을 옮기는 데 드는 비용을 모델로 적으면 다음과 같다.
설계의 핵심 결정은 "어떤 순서로 역을 방문하고, 어디서 싣고 내릴까"다. 두 가지 설계 결정을 제안한다. 설계 제안
train.cargos[]는 배열이라 어느 화물이든 unload로 꺼낼 수 있으므로 순서 자체가 강제는 아니지만 — 일찍 내릴 무거운 화물을 오래 싣고 다니면 그만큼 무거운 구간이 길어진다. 목적지가 가까운 무거운 화물을 우선 처리하는 것이 원칙 A의 직접 적용이다.아래는 한 방향 순회의 설계 스케치다. 실제 통과 코드가 아니라 — 비용 함수에서 연역한 의사코드에 가까운 C++다.
// 원형 트랙에서 두 위치 사이 최단 부호거리 (시계 +, 반시계 -)int shortStep(int from, int to) { int cw = (to - from + MAPSIZE) % MAPSIZE; // 시계 호 int ccw = MAPSIZE - cw; // 반시계 호 return (cw <= ccw) ? cw : -ccw; // 짧은 쪽 + 부호}// 화물들을 한 방향으로 트랙을 훑으며 싣고 내린다.void sweepDeliver() { // 각 역을 트랙 순서(위치 오름차순)로 정렬해 둔다. for (int step = 0; step < visitOrder.size(); ++step) { int st = visitOrder[step]; // 다음에 들를 역 move(shortStep(train.pos, station_pos[st])); // 그 역으로 이동 // ① 이 역이 목적지인 화물 먼저 내린다 (무게 감소) for (int id : onboardBoundTo(st)) unload(id); // ② 적재용량 안에서 실을 수 있는 화물을 싣는다 for (int id : cargoAt(st)) { // 진행방향 목적지 우선 if (train.weight + weightOf(id) <= 100) load(id); } } // 한 바퀴로 다 못 비우면 다음 묶음으로 다시 sweep}
train.weight가 줄어, 다음 구간을 더 가벼운 열차로 이동한다. 싣기를 먼저 하면 곧 내릴 화물의 무게까지 짊어진 채 출발하게 된다. 또한 load는 적재용량 100을 검사하므로 — 먼저 내려 공간을 비워야 더 많이 실을 수 있다. 두 이유 모두 원칙 A(무거울 때 짧게)와 원칙 B(많이 싣기)의 직접 귀결이다. cargoAt(st)를 "진행 방향 목적지 우선"으로 정렬하면, 곧 지나칠 역의 화물을 우선 실어 한 sweep 안에서 더 많이 배송한다. 설계 제안
한 바퀴 sweep으로 모든 화물을 비우지 못하는 경우 — 적재용량 100이 한 바퀴에 실을 수 있는 양을 제한하기 때문 — 묶음을 나눠 여러 번 sweep한다. 각 sweep은 "이번에 실을 화물 집합"을 정하고 그 집합만 처리한다. 어떤 화물을 어느 sweep에 넣을지가 §1의 1단계 "묶음 구성" 문제다.
역 N ≤ 100, 화물 총수 M은 역당 30~100개이므로 최대 ~10⁴다. 한 sweep은 트랙을 한 바퀴(거리 ≤ 1000) 도는 이동 + 각 화물의 load/unload 한 번씩이다. sweep 횟수는 — 무게 합 상한이 화물 총무게를 100으로 나눈 값에 비례하므로 O(\,\sum weight / 100\,) 회. 한 화물의 평균 무게가 약 38(%50·%100 절반씩이면 기댓값 ~38)이라면 M·38 / 100 ≈ 380·(M/10⁴) sweep 규모다. 각 sweep의 이동 비용은 (무게 ≤ 100 + 50)·(거리 ≤ 1000 + 10)로 상한이 잡힌다. 정확한 SCORE는 실측으로만 확정되나, "한 방향 sweep + 묶음"이 낱개 배송의 회송을 제거해 비용을 크게 낮추는 것이 설계의 전제다. 설계 제안
한 sweep은 적재용량 100의 제약 아래 화물 부분집합을 처리한다. 화물을 sweep에 배정하는 것은 본질적으로 bin packing이다 — 무게 합 100짜리 가방(sweep)에 화물을 채워 넣되, 가방 수(sweep 횟수)를 줄이려 한다. bin packing은 NP-난해지만, 이 문제에는 추가 구조가 있다 — 화물에는 무게뿐 아니라 출발역·목적지역이 있다.
한 sweep에 배정된 화물들이 동시에 열차에 실릴 수 있으려면, 어느 시점에든 열차 위 무게 합이 100을 넘지 않아야 한다. 주의: sweep 전체 무게 합이 아니라 — 화물이 실리고 내려지는 과정의 순간 최대값이 100 이하여야 한다.
그래서 같은 sweep이라도, 출발역이 앞쪽이고 목적지가 곧 뒤에 오는 화물들은 — 서로 겹치는 적재 구간이 짧아 무게 합이 100을 넘지 않고도 많이 묶을 수 있다. 출발역이 모두 앞에 몰리고 목적지가 모두 뒤에 몰리면, 중간 구간에서 모든 화물이 동시에 실려 무게가 정점을 찍는다.
이 관찰에서 묶음 구성의 휴리스틱이 나온다. 설계 제안
Theorem 1은 한 화물의 최단거리를 말하지만, sweep 전체의 방향은 또 다른 결정이다. 한 sweep이 처리하는 화물 묶음 전체를 보면 — 출발역과 목적지역이 트랙 위에 분포한다. 시계로 훑을 때와 반시계로 훑을 때 "출발역이 목적지역보다 진행 방향 앞에 오는" 화물의 비율이 다르다. 진행 방향 앞에 출발역이 오는 화물이 많은 방향을 택하면, 회송 없이 흡수되는 화물이 많아진다. 두 방향을 모두 시뮬레이션해 비용이 작은 쪽을 고르는 것이 안전하다 — sweep당 두 번 계산하는 비용은 작다.
break). 따라서 설계는 점수 최적화보다 완전성을 먼저 보장해야 한다 — 모든 화물을 빠짐없이 목적지에 내리고, process 종료 시 열차를 반드시 비운다. 묶음 구성이 아무리 정교해도 화물 하나를 빠뜨리면 0점이 아니라 음의 거대값이다. "먼저 안전하게, 그 다음 싸게"가 철칙이다.
| 전략 | 완전성 | 비용 경향 | 구현 | 평가 |
|---|---|---|---|---|
| 낱개 직송 (한 화물씩 출발→목적) | 보장 | 높음 | 쉬움 | 회송(빈 열차 복귀)이 화물 수만큼 누적 |
| 한 방향 sweep, 묶음 없음 | 보장 | 중간 | 쉬움 | 회송은 없으나 적재용량을 못 살려 sweep 횟수 과다 |
| 완전 최적 경로 (VRP 정수계획) | 보장 | 최소 | 불가 | 용량제약 라우팅은 NP-난해 — 시간 안에 못 풂 |
| 호 그룹핑 묶음 + 한 방향 sweep + 방향 선택 | 보장 | 설계 목표 | 중간 | 회송 제거 + 적재용량 활용 + 무거운 구간 단축 |
표의 구조는 §1의 분해를 비춘다. 완전성은 모든 화물을 load/unload로 짝지으면 어느 전략이든 얻는다(Invariant). 진짜 경쟁은 비용에서 벌어진다. 낱개 직송은 회송 비용이 화물 수만큼 쌓이고, 묶음 없는 sweep은 적재용량 100을 못 살려 같은 호를 여러 번 돈다. 완전 최적(용량제약 차량경로문제, CVRP)은 이론적 최소를 주지만 NP-난해라 10 TC를 시간 안에 못 끝낸다. 따라서 "호 구간별로 화물을 묶고, 한 방향으로 sweep하며, 두 방향 중 싼 쪽을 택하는" 설계가 — 통과 코드가 없는 상태에서도 비용 함수로부터 연역할 수 있는 현실적 최선이며, Lemma가 그 회송 흡수를 받친다.
|to − from|을 그대로 쓰면 트랙 둘레의 절반을 넘는 거리를 손해 본다. 반드시 min(cw, ccw)로 두 호 중 짧은 쪽을 택하고, move에는 그 호의 부호 있는 거리를 넘겨야 한다.
load 실패를 피한다.
verify()는 train.num > 0이면 즉시 실패다. 마지막 화물까지 unload로 내렸는지 확인하라. PENALTY 10¹⁴는 한 번의 누락으로 전체 채점을 0이 아닌 거대 음수 점수로 만든다.
verify()는 각 역의 화물 dest가 그 역 인덱스와 일치하는지 검사한다. unload는 아무 역에서나 호출 가능하므로, 목적지 역이 아닌 곳에 잘못 내리면 verify 실패다. 하역은 반드시 cargo.dest == train.pos인 역에서만.
이 문제는 통과 코드가 없으므로 측정된 SCORE를 제시할 수 없다. 대신 채점기의 판정 구조를 명시한다. verify()는 열차가 비었는지(train.num == 0)와 모든 화물이 제 목적지 역에 있는지를 검사한다. 하나라도 어기면 gTotalScore = PENALTY(10¹⁴) 후 break. 모두 통과하면 move가 누적한 gTotalScore가 그대로 최종 SCORE다 — 낮을수록 좋다.
move/load/unload·verify()로부터 연역한 설계다. sweepDeliver()·shortStep() 스케치는 컴파일·실측을 거치지 않았고, Theorem 2의 sweep 횟수·비용 상한은 무작위 화물 분포에 대한 추정에 의존한다. "원형 최단거리"와 "한 방향 sweep으로 회송 제거"는 비용 함수에서 안전하게 연역되지만, 정확한 SCORE와 최적 묶음 구성은 실제 구현·실행으로만 확정된다.