프로그래머스 택배 배달과 수거하기 python

프로그래머스 택배 배달과 수거하기 python

문제

트럭은 물류창고에서 출발하여 일렬로 나열된 n개의 집에 택배를 배달하고,
각 집에서 빈 상자를 수거한 뒤 다시 창고로 돌아와야 합니다.
트럭은 한 번에 최대 cap개의 상자를 실을 수 있으며,
deliveries[i]는 i+1번째 집에 배달할 상자의 개수,
pickups[i]는 i+1번째 집에서 수거할 상자의 개수를 의미합니다.

모든 배달과 수거를 완료하고 물류창고로 돌아올 때의 최소 이동 거리를 구하는 문제입니다.

---

아이디어

1. 가장 먼 집부터 처리
   가까운 집부터 처리하면 멀리 있는 집을 위해 여러 번 왕복해야 합니다.
   따라서 가장 먼 집부터 역순으로 확인하면서
   한 번 갈 때 최대한 많은 상자를 배달·수거하도록 해야 이동 횟수가 줄어듭니다.

2. 배달과 수거의 누적량 계산
   각 반복마다 deliver와 pickup에 남은 상자를 누적시켜
   아직 처리되지 않은 물량을 추적합니다.

3. 한 번에 처리 가능한 양(cap 단위)
   트럭이 한 번에 실을 수 있는 용량이 cap이므로
   남은 물량(deliver, pickup)이 0 이하가 될 때까지
   한 번 갈 때마다 (거리 * 2)만큼 이동 거리를 더합니다.

---

전체코드

def solution(cap, n, deliveries, pickups):
    answer = 0
    deliver = 0
    pickup = 0

    for i in range(n - 1, -1, -1):
        deliver += deliveries[i]
        pickup += pickups[i]

        while deliver > 0 or pickup > 0:
            deliver -= cap
            pickup -= cap
            answer += (i + 1) * 2

    return answer

---

풀이

초기 상태

cap = 4  
n = 5  
deliveries = [1, 0, 3, 1, 2]  
pickups = [0, 3, 0, 4, 0]

---

i = 4 (5번째 집)

deliver += deliveries[4] → 0 + 2 = 2  
pickup += pickups[4] → 0 + 0 = 0  

현재 남은 배달: 2, 수거: 0
→ 트럭은 최대 4개까지 실을 수 있으므로 한 번에 배달 가능.
따라서 이동 거리 = (4 + 1) * 2 = 10 추가.

이후:

deliver -= cap → 2 - 4 = -2  
pickup -= cap → 0 - 4 = -4  
answer = 10

---

i = 3 (4번째 집)

deliver += deliveries[3] → -2 + 1 = -1  
pickup += pickups[3] → -4 + 4 = 0

남은 배달: -1, 수거: 0
모두 0 이하이므로 while 실행 안 함.
즉, 이 구간은 추가 이동이 없습니다.

---

i = 2 (3번째 집)

deliver += deliveries[2] → -1 + 3 = 2  
pickup += pickups[2] → 0 + 0 = 0

남은 배달: 2, 수거: 0
→ 여전히 한 번 왕복으로 충분.
거리 = (2 + 1) * 2 = 6 추가.

이후:

deliver -= cap → 2 - 4 = -2  
pickup -= cap → 0 - 4 = -4  
answer = 10 + 6 = 16

---

i = 1 (2번째 집)

deliver += deliveries[1] → -2 + 0 = -2  
pickup += pickups[1] → -4 + 3 = -1

둘 다 0 이하 → 이동 없음.

---

i = 0 (1번째 집)

deliver += deliveries[0] → -2 + 1 = -1  
pickup += pickups[0] → -1 + 0 = -1

둘 다 0 이하 → 이동 없음.

---

최종 결과

answer = 16

---

결론

• 트럭은 가장 먼 거리(5번째 집)부터 역순으로 접근하며,
  배달과 수거를 한 번의 왕복으로 최대한 처리합니다.
• 각 거리에서 누적된 배달량과 수거량이 있을 때,
  while문이 cap 단위로 이를 모두 소진시킬 때까지 이동 거리를 더해줍니다.
• 이렇게 하면 한 번의 왕복으로 처리할 수 있는 최대 효율을 확보하게 되고,
  총 이동 거리 = 16이 됩니다.