[Programmers] - Python / 파이썬 - 택배 배달과 수거하기

문제

• https://school.programmers.co.kr/learn/courses/30/lessons/150369

시간 복잡도

• n만큼의 반복 * m만큼의 왕복 횟수 -> $O(n \cdot m)$
• n의 최댓값은 100,000이고, m의 최댓값은 50(원소의 최댓값이 50이고 cap의 최솟값이 1이기 때문에 최대 50번 반복)이기 때문에 충분하다.

문제 접근법

• 최소 이동 거리를 위해서는 가장 먼 곳 부터 배달을 해야한다.
• 가장 먼 곳 부터 배달할 상자의 개수와 회수할 상자의 개수를 따로 계산한다.
  (현재 위치에 배달할 상자나 회수할 상자가 남아 있는 경우, 한 번 더 왕복해야 하기 때문에 이를 위해서 둘을 따로 둔다.)
• 현재 위치의 이전 위치에 있는 집들은 어짜피 경로에 있기 때문에 고려하지 않고 뒤에서부터 탐색한다.

1. 현재 배달할 상자의 개수와 수거할 상자의 개수를 저장할 변수를 초기화한다.
2. 가장 먼 집부터 탐색을 시작한다.
   2-1. 현재 위치에 배달할 상자의 개수를 1번에서 초기화한 변수에 더한다.
   2-2. 현재 위치에서 회수할 상자의 개수를 1번에서 초기화한 변수에 더한다.
   2-3. 두 변수가 0 이하가 될 때 까지 최대 개수인 cap을 빼고, 왕복한 거리를 총 이동 거리에 더한다.
   (한 번 왕복하면 cap만큼 상자를 배달하고 회수할 수 있기 때문에, 1 이상의 수가 남으면 한 번 더 왕복해야 하기 때문)
3. 총 이동 거리를 출력한다.

코드

# Programmers
# Lv.2 - 택배 배달과 수거하기

def solution(cap, n, deliveries, pickups):
    ans = 0
    delivery = 0
    pickup = 0
    
    for i in range(n - 1, -1, -1):
        delivery += deliveries[i]
        pickup += pickups[i]
        
        while (delivery > 0 or pickup > 0):
            delivery -= cap
            pickup -= cap
            ans += (i + 1) * 2
    
    return ans