그리디, 누적합

1️⃣ 개념

1차원 리스트의 누적합

ex) 길이가 5인 리스트에서 0~2번째까지 N만큼 감소시키고 싶은 경우

[-N, 0, 0, N, 0, 0]

​
ex) 이후 1~3번째까지 M만큼 감소시키는 경우

[-N, -M, 0, N, M, 0]

2차원 리스트의 누적합

ex) 5x5 리스트에서 (0,0)~(2,2)까지 N만큼 감소시키고 싶은 경우

[[ -N,  0,  0,  N,  0,  0],
 [  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0],
 [  N,  0,  0, -N,  0,  0],
 [  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0]]

2️⃣ 문제 풀이

프로그래머스 택배 배달과 수거하기 (Level 2)

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

어차피 가까운 거리는 오는 길에 탐색할 수도 있으니까 먼 거리부터 탐색해야 한다!

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