[프로그래머스][level2] 택배 배달과 수거하기 - python

문제 링크

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

프로그래머스

 

풀이

- 그리디 문제

 이동 거리를 줄이기 위해서는 가장 멀리 있는 것부터 해결해야한다.

따라서 배달해야하는 택배 수와 수거해야하는 택배수를 더하고,

해당 위치를 방문하지 않아도 될 때까지 cap의 수만큼 빼준다. 

-> 왕복 이동하는 것을 의미하므로, 왕복 이동 거리를 더해준다. 

 

음수 값이어도 다음에 배달 & 수거할 택배들에 의해서 채워진다. 

def solution(cap, n, deliveries, pickups):
    answer = 0

    d = 0
    p = 0 
    
    # 먼 거리에 있는 택배부터 
    for i in range(n-1, -1, -1):
        d += deliveries[i]
        p += pickups[i]
		
        # 더이상 해당 위치까지 방문하지 않아도 될때까지 갱신 
        while d > 0 or p > 0 :
            d -= cap
            p -= cap
            answer += (i+1) * 2 

    
    return answer