🐢 택배 배달과 수거하기

1. 문제 링크

2023 KAKAO BLIND RECRUITMENT: 택배 배달과 수거하기

2. 코드

"""
택배 배달과 수거하기

💛 문제
당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 
배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.

배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 
또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)

트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 
트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 

각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 
트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 
각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 
각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 
이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

🧡 제한 사항
1 ≤ cap ≤ 50
1 ≤ n ≤ 100,000
deliveries의 길이 = pickups의 길이 = n
    deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
    pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
    0 ≤ deliveries의 원소 ≤ 50
    0 ≤ pickups의 원소 ≤ 50
트럭의 초기 위치는 물류창고입니다.


💚 입출력
cap	n	deliveries	          pickups         	      result
4 	5	[1, 0, 3, 1, 2]	      [0, 3, 0, 4, 0]	        16
2	  7	[1, 0, 2, 0, 1, 0, 2]	[0, 2, 0, 1, 0, 2, 0]	  30
"""

# 트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n
def solution(cap, n, deliveries, pickups):
  answer = 0

  # 현재 배달/수거 가능한 택배 개수
  deliver = 0   # 남은 배달 가능
  pick = 0   # 남은 수거 가능

  for i in range(n-1, -1, -1):
    cnt = 0

    # 해당 집까지 한 번 더 와야 함
    while deliver < deliveries[i] or pick < pickups[i]:
      # 몇 번 왔다 갔다 해야 하는지 횟수
      cnt += 1
      # 트럭에 실을 수 있는 최대 개수
      deliver += cap
      pick += cap
    deliver -= deliveries[i]
    pick -= pickups[i]

    # 배송/수거를 하면서 이동한 거리
    # 해당 위치까지 이동한 횟수(cnt)를 곱해준 뒤 answer에 더해준다
    answer += (i + 1) * cnt
    
    # 왕복 * 2
  return answer * 2

• 정확성

    테스트 1 〉	통과 (0.01ms, 10.1MB)
    테스트 2 〉	통과 (0.01ms, 10.2MB)
    테스트 3 〉	통과 (0.01ms, 10.2MB)
    테스트 4 〉	통과 (0.01ms, 10.1MB)
    테스트 5 〉	통과 (0.03ms, 10.2MB)
    테스트 6 〉	통과 (0.01ms, 10.2MB)
    테스트 7 〉	통과 (0.38ms, 10.4MB)
    테스트 8 〉	통과 (0.72ms, 10.2MB)
    테스트 9 〉	통과 (2.08ms, 10.1MB)
    테스트 10 〉통과 (1.87ms, 10.1MB)
    테스트 11 〉통과 (1.69ms, 10.3MB)
    테스트 12 〉통과 (1.57ms, 10.2MB)
    테스트 13 〉통과 (0.91ms, 10.1MB)
    테스트 14 〉통과 (1.22ms, 10.2MB)
    테스트 15 〉통과 (23.13ms, 11.8MB)
    테스트 16 〉통과 (271.49ms, 11.5MB)
    테스트 17 〉통과 (68.59ms, 11.4MB)
    테스트 18 〉통과 (31.40ms, 11.6MB)
    테스트 19 〉통과 (31.33ms, 11.6MB)
    테스트 20 〉통과 (34.18ms, 11.5MB)
  

3. 해설

뒤에서부터 택배, 수거를 시작한다

cap 보다 택배, 수거 수가 더 작다면 다시 시작점으로 가서 cap을 담을 수 있는 만큼 다시 초기화 해주고 cnt +=1 을 추가해준다

오는 길에 수거, 택배는 어차피 거리에 더해지기 때문에 마지막에 * 2 해줌으로써 거리를 구해줌