일렬로 늘어선 n개의 집에 택배를 배달하고 빈 상자를 수거해야 합니다. 트럭은 물류창고(0번 지점)에서 출발하며, 한 번에 최대 cap개의 상자만 실을 수 있습니다. 배달과 수거를 모두 마치고 창고로 돌아오는 최소 이동 거리를 구하는 문제입니다.
deliveries[i]— i+1번째 집에 배달할 상자 수pickups[i]— i+1번째 집에서 수거할 상자 수
문제를 어렵게 보이게 하는 것
처음 보면 “배달과 수거를 어떻게 섞어야 하지?”가 막막합니다. 배달을 먼저 다 하고 수거를 할지, 한 번 나갈 때 둘 다 할지, 어느 집부터 갈지 경우의 수가 너무 많아 보입니다.
여기서 문제를 풀리게 만드는 관찰이 두 가지 있습니다.
관찰 1 — 한 번 왕복하는 비용은 “가장 멀리 간 집”으로만 정해집니다.
창고에서 출발해 5번 집까지 갔다가 돌아오면 거리는 5 × 2 = 10입니다. 이때 1번, 3번, 4번 집을 들르든 말든 거리는 똑같습니다. 어차피 지나가는 길이기 때문입니다. 그러니 한 번 나갈 때는 갈 수 있는 만큼 최대한 처리하고 오는 것이 항상 이득입니다.
관찰 2 — 배달과 수거를 나눌 이유가 없습니다.
트럭은 배달용 적재 공간과 수거용 적재 공간을 따로 가진 셈입니다(배달할 상자를 내려놓은 자리에 빈 상자를 싣는다고 생각하면 됩니다). 그러니 한 번 나갈 때 배달도 cap개까지, 수거도 cap개까지 각각 처리할 수 있습니다. 둘을 따로 계산해도 되고, 그래야 문제가 단순해집니다.
이 두 관찰을 합치면 전략이 나옵니다.
가장 먼 집부터 역순으로, 트럭 용량만큼 묶어서 한 번에 처리한다.
왜 “가장 먼 집부터”인가
가까운 집부터 처리하면 어떻게 될까요? 3번 집을 먼저 처리하고 돌아온 뒤 5번 집을 처리하러 나가면 3×2 + 5×2 = 16입니다. 반대로 5번 집을 처리하러 나가는 길에 3번 집도 함께 처리하면 5×2 = 10으로 끝납니다.
즉 먼 집은 어차피 가야 하고, 가는 길에 가까운 집은 공짜로 처리됩니다. 그러니 항상 가장 먼 집을 기준으로 왕복을 잡고, 그 왕복에 최대한 많은 집을 끼워 넣는 것이 최적입니다. 이것이 이 문제의 그리디 근거입니다.
동작 과정 따라가기
cap = 4, deliveries = [1, 0, 3, 1, 2], pickups = [0, 3, 0, 4, 0] 인 경우를 보겠습니다.
1차 왕복 — 뒤에서부터 남은 일이 있는 집을 찾습니다.
deliveries = [1, 0, 3, 1, 2] 남은 배달 중 가장 먼 곳: index 4 (5번 집)
pickups = [0, 3, 0, 4, 0] 남은 수거 중 가장 먼 곳: index 3 (4번 집)
더 먼 쪽이 index 4 → 5번 집까지 왕복 = 5 × 2 = 10
이 왕복에서 용량 4만큼 배달하고, 용량 4만큼 수거합니다. 뒤에서부터 채웁니다.
배달: 5번 집 2개 → 4번 집 1개 → 3번 집 1개 (합 4, 용량 소진)
deliveries = [1, 0, 2, 0, 0]
수거: 4번 집 4개 (합 4, 용량 소진)
pickups = [0, 3, 0, 0, 0]
누적 거리 = 10
2차 왕복
남은 배달 중 가장 먼 곳: index 2 (3번 집)
남은 수거 중 가장 먼 곳: index 1 (2번 집)
더 먼 쪽이 index 2 → 3번 집까지 왕복 = 3 × 2 = 6
배달: 3번 집 2개 → 1번 집 1개 (합 3)
deliveries = [0, 0, 0, 0, 0]
수거: 2번 집 3개 (합 3)
pickups = [0, 0, 0, 0, 0]
누적 거리 = 10 + 6 = 16
배달과 수거 모두 비었으므로 종료, 답은 16입니다.
코드
public class ParcelDelivery {
public long solution(int cap, int n, int[] deliveries, int[] pickups) {
long answer = 0;
int delivery = n - 1; // 남은 배달이 있는 가장 먼 집을 가리키는 포인터
int pickup = n - 1; // 남은 수거가 있는 가장 먼 집을 가리키는 포인터
while (delivery >= 0 || pickup >= 0) {
// 이미 끝난 집은 건너뛰며 포인터를 앞으로 당긴다
while (delivery >= 0 && deliveries[delivery] == 0) delivery--;
while (pickup >= 0 && pickups[pickup] == 0) pickup--;
// 배달도 수거도 남지 않았으면 종료
if (delivery < 0 && pickup < 0) break;
// 이번 왕복의 비용은 둘 중 더 먼 집으로 결정된다
int maxDistance = Math.max(delivery, pickup) + 1;
answer += maxDistance * 2L;
// 그 왕복 안에서 배달과 수거를 각각 cap 만큼 처리한다
process(deliveries, delivery, cap);
process(pickups, pickup, cap);
}
return answer;
}
/** idx 부터 앞쪽으로 훑으며 최대 cap 개를 처리한다 */
private void process(int[] arr, int idx, int cap) {
int load = cap;
for (int i = idx; i >= 0 && load > 0; i--) {
if (arr[i] > 0) {
int moved = Math.min(arr[i], load);
arr[i] -= moved;
load -= moved;
}
}
}
}
코드 읽는 포인트
포인터를 되돌리지 않습니다. delivery와 pickup 포인터는 앞으로만 이동합니다. 한 번 0이 된 집은 다시 채워질 일이 없기 때문입니다. 바깥 while 루프가 여러 번 돌더라도 두 포인터가 배열을 훑는 총 횟수는 각각 n번을 넘지 않습니다 — 이것이 투 포인터입니다.
maxDistance는 +1을 합니다. 배열 인덱스는 0부터인데 집 번호(창고로부터의 거리)는 1부터이기 때문입니다. index 4는 5번 집, 거리 5입니다.
* 2L로 long 승격을 합니다. n이 최대 100,000이고 왕복이 여러 번이라 int 곱셈으로는 오버플로가 납니다. answer가 long이어도 오른쪽 곱셈이 int끼리면 그 시점에 이미 넘칩니다. 2L을 쓰는 이유입니다.
process는 배달과 수거에 그대로 재사용합니다. 두 배열의 처리 방식이 완전히 같기 때문입니다(“뒤에서부터 훑으며 cap만큼 덜어낸다”). 관찰 2에서 배달과 수거를 분리했기에 가능한 재사용입니다.
복잡도
| 항목 | 복잡도 |
|---|---|
| 시간 | O(n) — 두 포인터가 각각 배열을 한 번씩만 훑는다 |
| 공간 | O(1) — 입력 배열을 제자리에서 수정 |
바깥 while 안에 안쪽 반복문이 있어 O(n²)처럼 보이지만, process가 훑는 구간과 포인터가 전진하는 구간이 겹쳐 전체로는 각 원소를 상수 번만 건드립니다.
놓치기 쉬운 부분
- 입력 배열을 직접 수정합니다. 원본 보존이 필요한 상황이라면 복사본을 만들어야 합니다.
- 종료 조건을
&&가 아니라||로 씁니다. 배달은 끝났는데 수거가 남은 경우(혹은 반대)에도 계속 왕복해야 하기 때문입니다. - 첫
if (delivery < 0 && pickup < 0) break;가 필요합니다. 포인터를 당긴 뒤 둘 다 -1이 되면Math.max(-1, -1) + 1 = 0이 되어 거리 0짜리 왕복이 무한히 돌 수 있습니다.