[프로그래머스] 파이썬 - 택배 배달과 수거하기

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

# 조건

![[Algorithm/programmers/assets/Pasted image 20230522135228.png]]

• 당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다.
• 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
  • 배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
• 트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다.
• 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다.
• 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다.
• 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.
• 트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다.
• 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

# 접근 방법

• 먼 거리에서부터 최대한 많이 배달을 하고, 최대한 많이 수거해오면 된다.
• 그걸 위해서 배열을 먼저 뒤집고, 먼 집부터 탐색을 하며
  • 배달 -> d, 수거 -> p 에 갱신을 해주며 연산해준다.
• 우선 배달 또는 수거를 한 양 만큼 + 해주고, 음수가 될 때 까지 배달, 수거 작업을 해주면 된다.
  • 또한 작업을 할 때 마다 거리를 더해주면 된다.
  • 음수가 된 부분에서는 이전 작업에서 남았던 상자만큼 알아서 작업한 경우가 된다.
  • 즉 -3이 된다면, 돌아오는 길에 3개까지는 가는 길에 들고 오거나 배달할 수 있는 것이다.

def solution(cap, n, deliveries, pickups):  
    deliveries = deliveries[::-1]  
    pickups = pickups[::-1]  
    answer = 0  

    d = 0  
    p = 0  

    for i in range(n):  
        d += deliveries[i]  
        p += pickups[i]  

        while d > 0 or p > 0:  
            d -= cap  
            p -= cap  
            answer += (n - i) * 2  
    return answer