택배 배달과 수거하기
https://school.programmers.co.kr/learn/courses/30/lessons/150369
문제 설명
당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.
트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.
풀이
생각해 보면 cap이 감당 가능한 범위에서 제일 멀리 왕복하면 최소 이동거리를 구할 수 있습니다.
위 사진을 기준으로 우리는 처음 왕복 시 집 4, 5번의 배달 및 수거를 할 수 있는데 집 3번의 배달도 같이 수행 가능 합니다.
즉, cap개의 배달 상자를 담아서 거리가 먼 곳부터 주고 수거해오는 문제입니다.
def solution(cap, n, deliveries, pickups):
answer = 0
deliver = deliveries[::-1]
pickup = pickups[::-1]
sum_d = 0
sum_p = 0
for i in range(n):
sum_d += deliver[i]
sum_p += pickup[i]
# sum_d가 0보다 크다는 말은 cap보다 많은 수를 배달했다는 뜻
while sum_d > 0 or sum_p > 0:
sum_d -= cap
sum_p -= cap
answer += (n-i)*2
return answer