이 페이지는 100×100×100 공간에 흩어진 10만 개의 박스를 옮기는 풀이가 왜 통과하는가를 끝까지 따진다. 채점기의 verify()가 강제하는 "무게 단조 적층" 제약이 어떻게 문제를 정렬 문제로 환원시키는지, getHeight → getInfoAndArrange → destSort → build의 4단 파이프라인이 각 단계에서 어떤 불변식을 세우는지, 그리고 amax·bmax 경로 높이 비교가 왜 충돌 없는 비행을 보장하는지를, SCORE 228,823,384를 만든 실제 C++ 구현으로 라인 단위 해부한다.
드론배송의 점수는 pick·drop·move 호출 1회당 1점, 그 누적이다. 그러나 점수보다 먼저 통과해야 하는 것은 채점기 verify()다 — 단 하나의 박스라도 잘못 쌓이면 PENALTY 10조가 즉시 부과된다. 그러므로 베스트 해법을 이해하려면 점수 함수가 아니라 verify()의 두 조건부터 읽어야 한다.
조건 ①은 "모든 박스를 제 목적지 셀에 보내라"는 배송 요구다. 조건 ②가 진짜 난이도다 — 한 셀에 쌓인 스택은 아래로 갈수록 무거워야 한다. 즉 목적지 셀의 최종 스택은 무게 내림차순으로 정렬돼 있어야 한다. 이 한 줄이 문제 전체를 지배한다.
풀이의 process()는 정확히 네 단계로 분해된다. 각 단계는 다음 단계가 의지할 불변식을 하나씩 세운다.
A[r][c].pn을 기록한다. 드론은 박스 위로만 날 수 있으므로(빈손이면 z < h 금지), "올라갔다 내려가며" 높이를 읽는다.destX·destY·weight 정보를 알아내고(pick이 알려준다), 동시에 그 셀 안에서 박스를 prior 오름차순으로 다시 쌓는다.B[r][c].stk[]를 무게 내림차순으로 정렬한다. 이것이 조건 ②의 답을 미리 계산하는 단계다.핵심 통찰은 "정보 수집"과 "물리적 이동"이 분리되어 있다는 점이다. 드론은 실제 공간에서 박스를 한 번에 하나씩만 옮길 수 있지만, 풀이는 A[][]·B[][]라는 그림자 자료구조에 전체 박스 분포를 먼저 복원한다. 그 그림자 위에서 정렬을 끝낸 뒤, 마지막 단계에서만 실제 드론을 움직인다 — 계획과 실행의 분리다.
verify()가 "정렬된 상태"를 요구한다면, 문제의 본질은 배송이 아니라 정렬이다. 배송(목적지 이동)은 어떤 순서로 해도 조건 ①을 만족하지만, 조건 ②는 오직 무게 내림차순이라는 단 하나의 최종 배열만 허용한다. 그러므로 모든 설계 자원을 "어떤 순서로 쌓을 것인가"에 쏟아야 한다.
먼저 가장 약한 보장을 확인한다: 이 풀이는 반드시 10만 개 박스를 모두 옮기는가? 그리고 옮긴 결과가 조건 ②를 어김없이 만족하는가?
자료구조 Data의 stk[]는 후입선출(LIFO) 스택이다. pushA/pushB는 pn을 올리며 맨 위에 쌓고, pop은 맨 위만 뺀다. 드론의 물리적 제약 — 셀의 맨 위 박스만 pick할 수 있다(h != gDroneZ면 실패) — 이 곧 스택의 LIFO 규칙과 정확히 일치한다.
따라서 풀이 안의 A[r][c]·B[r][c] 스택 상태는 매 순간 실제 공간의 박스 더미 상태와 동기화된다. 그림자 자료구조와 실세계가 한 치도 어긋나지 않는다는 이 불변식이, 풀이가 "머릿속에서 계산한 대로" 드론을 움직여도 안전한 근거다.
목적지 셀 (r,c)에 도착할 박스 목록을 무게 내림차순으로 정렬한 뒤(destSort) 그 순서대로 차례로 쌓으면(build), 결과 스택은 아래에서 위로 무게가 비증가한다 — 즉 verify()의 조건 ②(weight[h] ≤ weight[h-1])를 빠짐없이 만족한다.
insertionSort(B[i][j].stk, ...)는 비교자 tg->w > stk[j]->w로 무게 내림차순 배열을 만든다. 그 결과 stk[0]이 가장 무겁고 stk[len-1]이 가장 가볍다.
build()는 for i = 0 … len-1 순서로 stk[i]를 집어 목적지에 drop한다. drop은 pushA를 호출해 스택 맨 위에 박스를 올린다. 따라서 i가 커질수록(= 가벼운 박스일수록) 더 위에 쌓인다. 높이 h에 쌓이는 박스는 정렬 인덱스 i = h의 박스이고, weight[stk[h]] ≤ weight[stk[h-1]]은 내림차순 정렬의 정의 그 자체다. 모든 셀이 같은 논리를 따르므로 조건 ②는 전역적으로 성립한다.
초기 상태에서 한 출발 셀의 박스 더미는 무작위 순서다. 드론은 맨 위 박스만 집을 수 있으므로(LIFO), 더미 바닥의 박스를 꺼내려면 위의 박스들을 전부 다른 곳으로 옮겨야 한다. 만약 박스를 "필요할 때마다" 꺼낸다면, 같은 셀을 여러 번 들쑤시며 같은 박스를 여러 번 옮기는 낭비가 생긴다. getInfoAndArrange()는 이 낭비를 막는다 — 한 셀을 딱 한 번 완전히 비웠다가, 다음 작업에 유리한 순서(prior 오름차순)로 다시 쌓는다.
Box::init()은 박스마다 prior 키를 만든다 — 목적지 행 er을 상위 비트, 목적지 열 ec(짝수 행은 99-ec로 뒤집어)를 중간 비트, 무게 w를 하위 비트에 넣은 비트팩 정수다.
행을 상위 비트에 둔 것은 "목적지 행 순서대로" 박스를 처리하기 위함이고, 짝수 행에서 열을 뒤집은 것은 뱀(boustrophedon) 경로를 만들기 위함이다 — 홀수 행은 왼→오, 짝수 행은 오→왼으로 훑으면 행을 바꿀 때 드론이 멀리 되돌아가지 않는다. prior 오름차순 정렬은 곧 "드론이 목적지들을 방문할 최적에 가까운 순서"를 만든다. 무게를 하위 비트에 둔 것은 같은 목적지 박스들끼리의 보조 정렬 키다.
이 문제에서 모든 비용은 호출 횟수다. 한 박스를 출발 셀에서 목적지 셀로 옮기는 데 드는 비용을 모델로 적으면 다음과 같다.
수평 이동량 |Δr|+|Δc|는 두 셀의 위치가 정해지면 바꿀 수 없는 하한이다. 절감의 여지는 수직 비용에 있다. 드론은 경로상의 모든 박스 더미를 넘어야 하므로, 경로 위 셀들의 최대 높이 maxH까지 올라갔다가 도착해서 내려온다. 그러므로 mymove()의 핵심은 "경로 위 최대 높이가 가장 낮은 경로를 고르는 것"이다.
L자 경로는 두 가지뿐이다 — 가로 먼저(행 고정 이동 후 열 고정 이동)와 세로 먼저. 풀이는 두 경로의 최대 높이 amax·bmax를 각각 계산해 더 낮은 쪽을 택한다.
// (sr, sc)에 있는 드론을 (er, ec)로 이동시킨다.void mymove(int sr, int sc, int er, int ec, int box) { int cc = sc < ec ? Right : Left; // 열 진행 방향 int rr = sr < er ? Back : Front; // 행 진행 방향 // 두 L자 경로 각각의 최대 높이 구하기 int i = sr, j = sc; int maxH = max(dronH, A[er][ec].pn + box); // 출발·도착 높이의 최대 int amax = maxH, bmax = maxH; for (; j != ec; j += dc[cc]) amax = max(amax, A[sr][j].pn + box); // 가로후세로 for (; i != er; i += dr[rr]) amax = max(amax, A[i][ec].pn + box); for (i = sr; i != er; i += dr[rr]) bmax = max(bmax, A[i][sc].pn + box); // 세로후가로 for (j = sc; j != ec; j += dc[cc]) bmax = max(bmax, A[er][j].pn + box); maxH = max(maxH, min(amax, bmax)); // 더 낮은 경로의 천장을 채택 while (dronH < maxH) move(Up), ++dronH; // 천장까지 한 번만 상승 if (amax < bmax) { // 가로 먼저 for (j = dronC; j != ec; j += dc[cc]) move(cc), dronC += dc[cc]; for (i = dronR; i != er; i += dr[rr]) move(rr), dronR += dr[rr]; } else { // 세로 먼저 for (i = dronR; i != er; i += dr[rr]) move(rr), dronR += dr[rr]; for (j = dronC; j != ec; j += dc[cc]) move(cc), dronC += dc[cc]; } if (box) { // 박스를 든 상태면 내려놓기 while (dronH > A[er][ec].pn + 1) move(Down), --dronH; drop(); A[er][ec].pushA(pickedBox); pickedBox = nullptr; }}
box 매개변수가 1이면 박스를 든 비행이다. move() 채점기 규칙상 박스를 들면 z > h(더미보다 한 칸 높게), 빈손이면 z ≥ h여야 통과한다. 그래서 경로 높이 계산에 + box가 더해진다 — 박스를 들었으면 모든 더미를 한 칸 더 높이 넘어야 하기 때문이다. 천장까지의 상승은 경로 시작에 딱 한 번만 일어난다. 매 칸마다 오르내리면 수직 move 호출이 폭증하므로, "한 번 올라가 직진, 도착해서 한 번 하강"이 수직 비용의 최소형이다.
이제 정보 수집의 심장 — getInfoAndArrange()다. 한 셀의 박스들을 어디로 흩어 놓았다가 다시 모을 것인가? 너무 멀리 흩으면 왕복 수평 비용이 커지고, 너무 가까이 모으면 그 셀들 자체가 높아져 수직 비용이 커진다. 풀이는 BFS()로 "현재 셀에서 가장 가까운 빈 셀들"을 정확히 박스 개수만큼 골라 한 박스씩 분산한다.
// (0,99) => (99,99)로 가며 각 셀 박스를 prior 오름차순으로 다시 담기void getInfoAndArrange() { int r = 0, c = 99, dir = 1; while (1) { BFS(r, c, A[r][c].pn); // (r,c) 주변 pn개의 빈 셀 좌표 수집 for (int i = 1; i < re; ++i) { // 박스를 한 개씩 인근 셀로 분산 mymove(dronR, dronC, r, c, 0); mypick(); // 들춰서 destX/Y/weight 정보 획득 que[i].prior = pickedBox->prior; // 각 박스 prior 저장 mymove(dronR, dronC, que[i].r, que[i].c, 1); } queSort(); // prior 오름차순 정렬 for (int i = 1; i < re; ++i) { // 정렬된 순으로 (r,c)에 다시 쌓기 mymove(dronR, dronC, que[i].r, que[i].c, 0); mypick(); mymove(dronR, dronC, r, c, 1); } if (r == 99 && c == 98) break; // 뱀 경로로 다음 셀 진행 if (c + dc[dir] < 0) ++r, dir = 0; else if (c + dc[dir] > 99) ++r, dir = 1; else c += dc[dir]; }}
A[r][c].pn개의 가장 가까운 빈 셀을 골라준다. 가까운 셀에 흩으면 분산-재수집 왕복의 수평 비용이 최소화되고, 한 박스씩 분산하므로 그 셀들이 1층 이상 높아지지 않아 수직 비용도 억제된다. 분산 단계에서 pick은 박스를 들추며 채점기로부터 목적지·무게를 알려주는데(mypick이 처음 본 박스를 box[]·B[][]에 등록), 이때 prior가 정해진다. 흩어 놓은 뒤 queSort로 정렬하고 같은 셀에 되돌려 쌓으면, 그 셀의 더미가 prior 오름차순으로 정돈된다.
박스 총수 B = 10⁵다. 각 박스는 파이프라인에서 상수 번 — 정보수집 분산 1회, 재수집 1회, 최종 build 시 1~2회 — 옮겨지므로 총 운반 횟수는 O(B)다. 운반 1회의 비용은 수평 이동 |Δr|+|Δc| ≤ 198 + 수직 비용 + 상수(pick·drop)다. 무작위 분포에서 한 셀의 평균 박스 수는 B / 10⁴ = 10개이므로 더미 높이의 평균은 낮고, BFS 분산이 인근 셀을 쓰므로 평균 수평 이동도 작다. 측정 SCORE 228,823,384는 CUT 250,000,000 대비 8.5% 여유로, 이 상수 인자가 실제로 작게 유지됨을 보여준다.
move() 규칙을 다시 보자 — 빈손이어도 드론은 z ≥ h여야 한다. 셀 위에 박스가 있으면 그 위로 날아야 한다. 그런데 최종 build() 단계에서 목적지 셀에 박스를 쌓다 보면, 드론이 작업 중인 셀에 "이미 쌓다 만 박스 더미"가 남아 있을 수 있다. 그 더미를 건드리지 않고 다음 박스를 그 위에 정확한 위치로 끼워 넣는 것은 불가능하다 — 스택은 LIFO이므로 중간에 삽입할 수 없다.
build(pr, pc, ...)는 직전 위치 (pr,pc)를 인자로 받는다. 현재 드론이 선 셀에 남은 박스가 있으면(cnt = A[dronR][dronC].pn > 0), 그 박스들을 인접한 제3의 셀 (nr,nc)로 역순으로 옮겼다가 다시 (pr,pc)로 원래 순서로 옮겨 빈자리를 만든다 — sendN 두 번.
스택을 한 번 옮기면 순서가 뒤집힌다(LIFO). 두 번 옮기면 원래 순서로 복원된다. 이 "역순 백업 → 정순 복귀" 2회 이동이, 작업 셀을 깨끗이 비우면서도 옮겨진 더미의 무게 단조성을 보존하는 유일한 방법이다.
void build(int pr, int pc, Box* stk[], int len) { int cnt = A[dronR][dronC].pn; if (cnt) { // 작업 셀에 남은 박스가 있다면 int nr = pr, nc = pc; for (int d = 0; d < 4; ++d) { // (pr,pc)가 아닌 인접 셀 찾기 nr = dronR + dr[d], nc = dronC + dc[d]; if (nr < 0 || nr >= LM || nc < 0 || nc >= LM) continue; if (nr == pr && nc == pc) continue; break; } sendN(dronR, dronC, nr, nc, cnt); // 역순으로 백업 sendN(dronR, dronC, pr, pc, cnt); // 원래 순서로 (pr,pc)에 복귀 } // 같은 값 처리를 위해 현재 위치를 복사 for (int i = 0; i < len; ++i) rows[i] = stk[i]->sr, cols[i] = stk[i]->sc; for (int i = 0; i < len; ++i) { // 정렬 순서대로 목적지에 적층 mymove(dronR, dronC, rows[i], cols[i], 0); mypick(); mymove(dronR, dronC, stk[0]->er, stk[0]->ec, 1); // 목적지는 모두 동일 }}
(99,99,99)다. getInfoAndArrange()는 (99,98)에 도달했을 때 (99,99)의 박스를 모두 (99,98)로 옮겨 (99,99)를 의도적으로 비운다. 이렇게 하면 process()의 최종 적층 루프가 (99,99)→(0,99)를 뱀 경로로 훑을 때, 시작 셀 (99,99)가 깨끗해 build의 역순 백업이 불필요해진다. 작은 사전 정리 한 번이 마지막 단계 전체를 단순화한다.
드론은 박스 위로만 날 수 있으므로(빈손 z ≥ h), 한 셀의 높이를 알려면 move(Down)이 실패할 때까지 내려가 본다 — 더 못 내려가는 높이가 곧 그 셀의 박스 더미 높이다. getHeight()는 이 "내려가 보기"를 100×100 뱀 경로의 모든 셀에 적용해 A[r][c].pn을 채운다. 옆 셀로 이동할 때 move(dir)가 실패하면(옆 셀 더미가 더 높음) 한 칸 올라가 다시 시도한다(while(move(dir)==false) ++dronH, move(Up)). 이 단계가 끝나야 mymove()의 경로 높이 계산이 정확한 데이터를 갖는다.
| 전략 | verify | 호출 수 경향 | 구현 | 평가 |
|---|---|---|---|---|
| 즉시 운반 (정렬 없이 보이는 대로) | 실패 | PENALTY | 쉬움 | 무게 역전 발생 — 조건 ② 위반으로 즉시 10조 |
| 목적지마다 매번 재정렬 | 통과 | CUT 초과 | 중간 | 같은 박스를 수십 번 들쑤심 — 호출 폭증 |
| 전역 최적 운반 순서 (TSP류) | 통과 | 최소 | 불가 | 10만 박스 적층-순서 동시최적화는 시간 안에 못 풂 |
| 4단 파이프라인 (수집→prior정렬→무게정렬→build) | 통과 | 228,823,384 | 중간 | 각 박스 상수 회 운반 + 뱀 경로 + 경로높이 최소화 |
표의 구조는 §1의 분해를 그대로 비춘다. verify 통과는 "무게 내림차순으로 쌓기"만 지키면 공짜로 얻는다(Theorem 1). 진짜 경쟁은 호출 수에서 벌어진다. 정렬 없는 즉시 운반은 verify조차 못 넘고, 매번 재정렬은 같은 박스를 반복해 옮겨 CUT을 초과한다. 전역 최적은 이론적 최소지만 10만 박스 규모에서 시간 안에 불가능하다. 따라서 "각 박스를 상수 번만 옮기되, 뱀 경로와 경로 높이 비교로 그 상수 인자를 작게" 만드는 4단 파이프라인이 현실적 최선이며, Theorem 2가 그 선형 상한을 보장한다.
move()는 빈손이면 z ≥ h, 박스를 들면 z > h를 요구한다. 경로 높이 계산에서 A[..][..].pn + box의 +box를 빼먹으면, 박스를 든 채 더미와 같은 높이로 날다 move가 실패한다.
prior = (er<<18) | (ec<<10) | w에서 w는 1~1000(10비트), ec는 0~99(7비트면 충분하나 8비트 슬롯)다. 비트 폭이 겹치면 정렬 키가 오염된다. 각 필드 최댓값에 맞춰 시프트 양을 정하라.
ec를 99-ec로 뒤집어야 한다. 반전을 빼면 행을 바꿀 때마다 드론이 격자 끝에서 끝으로 되돌아가 수평 move가 2배가 된다.
sendN 2회)을 빠뜨리면 무게 단조성이 깨져 verify가 PENALTY를 부과한다. (99,99) 사전 비우기와 build의 백업 로직 둘 다 필요하다.
이 풀이가 "통과한다"는 주장의 근거는 추측이 아니라 채점기 출력이다. 채점기는 pick/drop/move 호출 시점마다 gTotalScore를 1씩 올리고, 10개 TC가 끝난 뒤 verify()로 무게 단조·목적지 일치·박스 총수를 검사한다.
main.cpp는 seed = 5 고정으로 10개 TC를 생성한다. g++ -O2로 main.cpp + user.cpp를 함께 컴파일해 실행하면 SCORE: 228823384 과 PASS가 출력된다. 점수가 호출 횟수의 직접 누산이므로, 이 숫자는 풀이의 객관적 성적표다. 여유가 8.5%로 다른 문제보다 좁은 편이라, 운반 횟수를 늘리는 사소한 비효율도 누적되면 CUT을 위협할 수 있음에 유의하라.