이 페이지는 minimax 목적함수가 왜 균등 배정을 무력화하는지, NN 그리디가 만든 초기 해의 "천장(ceiling)"을 1-swap balancing이 어떻게 단조 감소시키는지를 끝까지 따진다. riseScore > diffCost 한 줄의 pruning이 무엇을 보장하는지, 세 가지 위치 케이스(맨앞·가운데·맨뒤)의 비용 미분식이 어떻게 유도되는지를 실제 통과 C++ 코드로 라인 단위 해부한다.
택시배정의 점수는 채점기 verify()가 결정한다. 각 택시 i의 운행 거리 cost(i)를 모두 계산한 뒤 그 중 최댓값만 TC 점수로 누적한다 — if (TC_SCORE < score) TC_SCORE = score;. 합도, 평균도 아니다. 목적함수는 minimax다.
이 한 줄의 정의가 직관을 거꾸로 뒤집는다. 합 최소화 문제라면 "모든 택시에 골고루 나눠라"가 좋은 출발점이다. 그러나 minimax에서는 골고루 나누는 것 자체가 함정이다. 99대의 택시가 완벽하게 균등해도, 단 한 대가 외진 승객 하나에 끌려가 폭주하면 그 한 대가 점수 전부다. 나머지 99대의 노력은 점수에 흔적조차 남기지 못한다.
그러므로 베스트 해법은 두 개의 명확히 분리된 단계로 설계된다.
핵심 통찰은 두 단계가 서로 다른 양을 최적화한다는 것이다. 1단계는 총합을 적당히 줄이는 휴리스틱이고, 2단계는 오직 최댓값만 집요하게 깎는다. minimax 점수를 직접 공략하는 것은 오직 2단계뿐이며, 1단계는 그 공략이 시작될 수 있는 발판을 마련할 뿐이다.
가장 먼저 확인할 것은 가능성(feasibility)이다. 점수보다 우선, 채점기 verify()는 한 승객이 두 번 배정되거나(isFinished==1 재방문) 한 명이라도 미배정이면 즉시 false를 반환해 PENALTY 10¹³을 부과한다.
1단계 종료 시점에 다음이 성립한다: 모든 승객은 정확히 하나의 택시 경로에 속하고, 어떤 승객도 두 경로에 동시에 속하지 않는다.
1단계 루프는 while (assignedCnt < passengerCnt)로 모든 승객이 소진될 때까지 돌고, 매 반복은 isFinished가 0인 승객만 후보로 삼은 뒤 즉시 1로 표시한다. 따라서 각 승객은 정확히 한 번 배정된다.
2단계 swap은 한 승객을 한 경로에서 빼고 다른 경로에 끼우는 이동이므로 — 총 배정 수도, 배타성도 보존한다. 이 불변식은 1단계 끝부터 assign_driver 호출까지 깨지지 않는다.
흔한 오해부터 정리한다. "minimax니까 모든 택시 비용을 똑같이 맞추면 그게 최적 아닌가?" — 아니다. 균등성은 필요조건도 충분조건도 아니다. 반례는 단순하다. 외진 곳에 떨어진 승객 한 명의 픽업+운행 거리가 그 자체로 80,000,000이라고 하자. 이 승객이 어느 택시에 가든 그 택시 비용은 최소 80,000,000이다. 모든 택시를 80,000,000으로 "균등하게" 맞춰봐야 점수는 80,000,000이다. 그러나 그 외진 승객을 이미 그 근처를 지나는 택시에 끼워 넣으면 추가 비용이 거의 0이고, 점수는 그 택시의 원래 비용 수준으로 떨어진다. 균등화는 천장을 낮추지 못한다 — 천장을 만든 그 승객을 어디에 두느냐가 전부다.
현재 해의 최댓값을 M = maxi cost(i)라 하자. 코드의 swap 채택 조건 nowLeft < M ∧ nowRight < M(즉 src·trg 양쪽 새 비용이 모두 M 미만)을 통과한 swap만 적용한다면, swap 후의 새 최댓값 M'은 반드시 M' ≤ M이다. 그리고 swap된 두 택시 중 적어도 하나가 원래 M을 만든 택시였다면 M' < M, 즉 천장이 진짜로 내려간다.
swap은 정확히 두 택시 src(가장 비싼)와 trg(가장 싼)의 경로만 바꾼다. 나머지 n-2대의 비용은 불변이다.
이 n-2대 각각의 비용은 정의상 모두 ≤ M이다(M이 최댓값이므로). swap 후 src·trg의 새 비용 nowLeft·nowRight도 채택 조건에 의해 둘 다 < M이다. 따라서 swap 후 모든 택시 비용이 ≤ M이고, 그 중 src·trg는 strict하게 < M이다. 새 최댓값 M' = max(불변 택시들, nowLeft, nowRight) ≤ M.
이것이 1-swap balancing의 심장이다. 채택 조건이 단지 "양쪽이 더 좋아진다"가 아니라 "양쪽 새 비용이 모두 현재 천장 아래"라는 점에 주목하라. 후자는 전자보다 엄격하다. 비싼 택시가 살짝만 가벼워지고 싼 택시가 천장 위로 솟구치는 swap은, 둘의 합이 줄어도 거부된다 — 천장을 깎지 못하기 때문이다. 코드는 이 조건을 두 겹으로 건다.
코드는 후보 swap을 두 가지 부등식으로 거른다.
(1) riseScore > diffCost → 기각. diffCost = cost(src) − cost(trg). trg에 승객을 끼워 늘어나는 비용 riseScore가 두 택시의 격차보다 크면, trg가 src를 추월해 새 천장이 된다. 채택해도 손해.
(2) riseScore + cost(trg) > cost(src) + loseScore → 기각. 좌변은 swap 후 trg 비용, 우변은 swap 후 src 비용(loseScore는 음수 — src에서 승객이 빠지며 줄어드는 양). trg의 새 비용이 src의 새 비용보다 크면, 두 택시 중 더 무거운 쪽이 여전히 무겁다는 뜻 — 천장 개선 폭이 보장되지 않는다.
두 부등식을 모두 통과한 (ii, jj) 쌍만이 "천장을 진짜로 내리는" 후보다. 그 중 riseScore가 가장 작은 것을 고른다.
먼저 1단계. NN 그리디는 매 반복마다 두 번의 선형 스캔을 한다 — (a) 현재 가장 적게 달린 택시를 찾고, (b) 그 택시 위치에서 가장 가까운 미배정 승객을 찾는다. 가장 적게 달린 택시에 우선권을 주는 것은 1단계 차원의 약한 균형화로, 2단계의 출발점을 너무 치우치지 않게 한다.
while (assignedCnt < passengerCnt) { // (a) 가장 적게 이동한 택시 찾기 shortTaxiId = 0; shortTaxiCost = taxiSCORE[0]; for (int i = 1; i < driverCnt; ++i) { if (taxiSCORE[i] < shortTaxiCost) { shortTaxiId = i; shortTaxiCost = taxiSCORE[i]; } } // (b) 그 택시에서 가장 가까운 미배정 승객 찾기 shortTaxiCost = PENALTY; shortPassId = -1; for (int i = 0; i < passengerCnt; ++i) { if (isFinished[i]) continue; int nowCost = getDist(driverList[shortTaxiId], passengerList[i].departure); if (nowCost < shortTaxiCost) { shortTaxiCost = nowCost; shortPassId = i; } } // 배정 확정: 픽업거리 + 승객 자체 운행거리를 누적 assignList[shortTaxiId][assignListSize[shortTaxiId]++] = shortPassId; taxiSCORE[shortTaxiId] += getDist(driverList[shortTaxiId], passengerList[shortPassId].departure) + passSCORE[shortPassId]; driverList[shortTaxiId] = passengerList[shortPassId].arrival; isFinished[shortPassId] = 1; assignedCnt++; }
passSCORE[i]는 승객 자신의 출발→도착 거리로, 어느 택시가 태우든 변하지 않는 고정 비용이다. 미리 한 번 계산해 둔다. 택시가 "선택할 수 있는" 유일한 가변 비용은 픽업 거리(이전 하차 지점 → 다음 승객 출발점)뿐이다. 그래서 (b)의 최근접 탐색이 departure까지의 거리만 본다 — 거리 metric은 맨해튼 거리(ABS(dy)+ABS(dx))다.
이제 2단계의 핵심 — swap 비용 미분이다. 한 승객을 경로에서 빼거나 끼울 때 비용이 얼마나 변하는지는 그 승객이 경로의 어디에 있느냐에 따라 세 가지 케이스로 갈린다. 경로를 좌표열 drv → p₀ → p₁ → … → pk-1로 보면, 한 승객은 "들어오는 간선"과 "나가는 간선"을 가진다.
for (int jj = 0; jj <= trgN; ++jj) { // 맨뒤(=trgN)까지 가능 if (jj == 0) { // trg 경로의 맨앞에 끼움 trgNowPassId = assignList[trgId][jj]; riseScore = getDist(passengerList[nowPassId].departure, driverListOrg[trgId]) + passSCORE[nowPassId] + getDist(passengerList[trgNowPassId].departure, passengerList[nowPassId].arrival) - getDist(passengerList[trgNowPassId].departure, driverListOrg[trgId]); } else if (jj == trgN) { // trg 경로의 맨뒤에 붙임 trgPrevPassId = assignList[trgId][jj - 1]; riseScore = passSCORE[nowPassId] + getDist(passengerList[nowPassId].departure, passengerList[trgPrevPassId].arrival); } else { // 가운데 — 한 간선을 끊고 둘로 가름 trgNowPassId = assignList[trgId][jj]; trgPrevPassId = assignList[trgId][jj - 1]; riseScore = getDist(passengerList[nowPassId].departure, passengerList[trgPrevPassId].arrival) + passSCORE[nowPassId] + getDist(passengerList[trgNowPassId].departure, passengerList[nowPassId].arrival) - getDist(passengerList[trgNowPassId].departure, passengerList[trgPrevPassId].arrival); } if (riseScore > diffCost) continue; // pruning ① if (riseScore + taxiSCORE[trgId] > taxiSCORE[srcId] + loseScore) continue; // pruning ② if (riseScore < nowBestRiseScore) { // 더 싼 삽입 위치 갱신 bestSrcIdx = ii; bestTrgIdx = jj; bestLoseScore = loseScore; nowBestRiseScore = bestRiseScore = riseScore; } }
prev.도착 → next.출발 하나가 있었다(비용 dist(next.출발, prev.도착)). 승객 p를 끼우면 이 간선이 사라지고 세 조각이 생긴다: prev.도착 → p.출발(픽업), p.출발 → p.도착(승객 자체 = passSCORE), p.도착 → next.출발(다음 픽업). 따라서 순증가 = (새 세 조각의 합) − (없어진 한 간선). 맨앞은 prev 대신 택시 원점(driverListOrg), 맨뒤는 next가 없어 빼는 항이 사라진다. src에서 빼는 loseScore는 같은 논리의 부호 반전이다.
1단계는 승객 수 K ≤ 10⁴회 반복하고, 매 반복이 택시 스캔 O(M) + 승객 스캔 O(K) = O(M+K)다. 1단계 총비용 O(K(M+K)) ≈ 10⁴ · 10⁴ = 10⁸. 2단계는 500회 반복, 매 반복이 src 승객 × trg 위치 = O(srcN · trgN)이며 두 경로 길이의 곱은 평균적으로 작다(K/M ≈ 100대씩이므로 ~10⁴). 2단계 총비용 ~500 · 10⁴ = 5×10⁶로 1단계에 비해 무시할 수 있다. 5 TC를 합쳐도 ~5×10⁸ 연산 — -O2에서 시간 안에 든다.
2단계 루프는 명목상 500회지만, 실제로는 그 전에 끝날 수 있다. 코드는 매 반복 시작 시 bestRiseScore를 거대한 상수 RiseMax = 9,000,000으로 초기화한다. 그 반복에서 두 pruning을 모두 통과하는 후보가 단 하나도 없으면 bestRiseScore는 RiseMax 그대로이고, 코드는 if (bestRiseScore >= RiseMax) break;로 즉시 탈출한다.
break가 발동했다는 것은: 현재 가장 비싼 택시에서 어떤 승객을 빼서 가장 싼 택시의 어느 위치에 넣어도, 천장을 내리는 swap이 존재하지 않는다는 뜻이다. 이는 1-swap 이웃 안에서의 국소 최적(local optimum)에 도달했음을 의미한다.
주의: 이것은 전역 최적이 아니다. 2개 이상의 승객을 동시에 옮기거나, src·trg가 아닌 다른 택시 쌍을 건드리면 더 내려갈 여지가 남아 있을 수 있다. 그러나 1-swap 국소 최적은 충분히 좋은 해이며, PASS CUT을 통과한다.
2단계는 모든 택시 쌍을 고려하지 않는다. 매 반복 가장 비싼 src와 가장 싼 trg 단 한 쌍만 본다. 이것은 minimax의 구조에서 곧바로 따라 나온다. 천장을 내리려면 천장을 만든 택시(=가장 비싼)에서 무언가를 빼야 한다 — 다른 택시를 가볍게 해봐야 점수는 그대로다. 그리고 빼낸 승객을 받을 곳은 diffCost(여유 격차)가 가장 큰 택시, 즉 가장 싼 택시여야 pruning ①을 통과할 확률이 높다. src·trg 선택은 휴리스틱이 아니라 minimax 목적의 직접적 귀결이다.
RiseMax = 9,000,000은 (1) "아직 후보 없음"을 나타내는 sentinel이자 (2) nowBestRiseScore의 초기 상한으로 쓰인다. 단, 코드가 실제 채택 상한으로 쓰는 값은 nowBestRiseScore = (int)diffCost로 매 ii마다 갱신된다 — 진짜 채택 게이트는 diffCost이고 RiseMax는 종료 판정용 sentinel이다. 두 역할이 한 상수에 겹쳐 있어 코드를 처음 읽을 때 혼동하기 쉬운 지점이다.
| 전략 | 가능성 | 천장 품질 | 구현 | 평가 |
|---|---|---|---|---|
| 균등 배정 (round-robin) | 보장 | 나쁨 | 쉬움 | 외진 승객이 한 택시를 폭주시켜도 손대지 못함 |
| NN 그리디만 | 보장 | 중간 | 쉬움 | 총합엔 좋으나 막판 외진 승객이 천장을 만듦 |
| 완전 minimax 최적 (ILP) | 보장 | 최소 | 불가 | 경로 포함 배정은 NP-난해 — 시간 안에 못 풂 |
| NN 그리디 + 500 1-swap balancing | 보장 | CUT 통과 | 중간 | 싼 출발점 + 천장만 집요하게 깎는 국소 탐색 |
표의 구조는 §1의 분해를 그대로 비춘다. 가능성은 어떤 배정이든 거의 공짜로 얻는다(Invariant). 진짜 경쟁은 천장 품질에서 벌어진다. 균등 배정은 천장을 만든 승객을 손댈 메커니즘이 없어 탈락하고, NN 그리디만으로는 막판 외진 승객 문제가 남는다. 완전 minimax 최적해(정수계획)는 이론적 최소를 주지만 경로가 포함된 배정 문제는 NP-난해라 시간 제약을 못 넘는다. 따라서 "NN으로 발판을 만들고, 1-swap으로 천장만 단조 감소"시키는 조합이 현실적 최선이며, Theorem 1이 그 단조성을 보장한다.
jj = 0 … trgN으로 경로 길이 + 1가지다. 맨뒤(jj == trgN)를 빼먹으면 가장 자연스러운 "꼬리에 붙이기"를 놓친다. 루프 조건이 jj <= trgN(미만이 아닌 이하)이어야 한다.
next가 없어 뺄 간선이 없고, 맨앞은 prev 대신 택시 원점을 쓴다. 세 케이스를 한 식으로 뭉뚱그리면 존재하지 않는 인접 승객을 참조해 비용이 틀어진다.
getDist(arrival, departure)를 다시 부르면 2단계가 느려진다. run() 초입에서 passSCORE[]로 한 번만 캐시하라.
riseScore > diffCost만으로는 부족하다. trg가 src를 추월하지 않더라도, swap 후 trg가 src보다 무거우면 두 택시 중 더 무거운 쪽이 바뀐 것뿐 — 천장 개선 폭이 보장되지 않는다. riseScore + cost(trg) ≤ cost(src) + loseScore 조건이 Theorem 1의 strict 감소를 받친다.
bestSrcIdx부터 왼쪽으로 당기고, trg 배열은 bestTrgIdx까지 오른쪽으로 밀어 빈자리를 만든다. 두 방향을 헷갈리면 경로 순서가 깨지고 다음 swap의 미분식이 전부 어긋난다.
이 풀이가 "통과한다"는 주장의 근거는 추측이 아니라 채점기 출력이다. 채점기 verify()는 5개 TC 각각에서 minimax 점수(TC_SCORE)를 계산해 SCORE에 누적하고, 최종 SCORE를 PASS CUT과 비교한다.
main.cpp는 seed = 5 고정에 5개 TC를 생성한다(make_tc). g++ -O2로 main.cpp + user.cpp를 함께 컴파일해 실행하면, verify()가 누적한 SCORE가 432'500'000 이하임을 확인하고 PASS를 출력한다. 채점기가 각 TC의 minimax 점수를 직접 누산하므로, 이 판정은 풀이의 객관적 성적표다. 단, 제출본의 printf 디버그 출력은 채점 환경에서 제거하거나 표준출력 부담을 고려해야 한다.