문제

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

풀이

아이디어

처음에 heap으로도 해보고 그랬으나 시간초과 및 오답이 줄줄 나와서 다른사람의 아이디어를 참고했다.

• 우선 가장 먼 곳부터 탐색하기 위해서 각 리스트를 거꾸로 뒤집어준다.
• 배달해야 할 것들의 개수를 d, 수거해야 할 것들의 개수를 p라고 하자.
• 인덱스 i를 0부터 n-1까지 증가시키면서 다음과 같은 로직을 수행한다.
  • d += deliveries[i]
    p += pickups[i]
  • 만약, 배달해야 할 것들이 있거나(d > 0), 수거해야 할 것들이 있다면 (p > 0) 택배차(?)를 불러서 배달하게 하거나, 수거하게 합니다. 이때, 택배차의 캐퍼시티(cap)만큼, 즉 최대로 배달하거나 수거하게 합니다.
  • 택배차가 왔다는 것은, 온 만큼 되돌아가야 한다는 뜻이므로 answer에 값을 업데이트해줍니다.

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

  • d나 p가 음수가 되어도 "미리 배달/수거 한 것"이기 때문에 괜찮습니다.

코드

def solution(cap, n, deliveries, pickups):
    answer = 0
    deliveries = deliveries[::-1]
    pickups = pickups[::-1]
    
    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