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

프로그래머스

이 문제가 그리디라고는 집작은 했지만 이해가 잘 되지 않았다.

이 문제의 키워드는 멀리 있는 집부터 무조건 해치우면 된다.

솔직히 한번에 이 아이디어가 떠오르지는 않지만 지래 겁먹고 예제 2를 확인안해서 둘다 멀리있는것 부터 하는구나...라는공통점을 못본 것은 내 실수라고 생각한다.

풀이는 아래와 같다.

def solution(cap, n, deliveries, pickups):
    deliveries = deliveries[::-1] # 배달 뒤집기
    pickups = pickups[::-1]       # 수거 뒤집기
    answer = 0

    d = 0 # 배달
    p = 0 # 수거

    for i in range(n):
        d += deliveries[i]
        p += pickups[i]

        while d > 0 or p > 0: #if가 아니고 while인 이유는 d랑 p랑 엄청 크면 계속 돌면서 answer에 더해줘야 하기 때문
            d -= cap # 갈 때 cap만큼 가져갈 수 있음
            p -= cap # 올 때 cap만큼 가져올 수 있음
            answer += (n - i) * 2 # 뒤집었기 때문에 (n-i)이고 *2한 이유는 왔다 갔다 이기 때문
    return answer