(Python/LV2) 택배배달과 수거하기

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/150369

프로그래머스

풀이:

 

def solution(cap, n, deliveries, pickups):
    answer = 0
    while deliveries or pickups:
        while deliveries and deliveries[-1] == 0:
            del deliveries[-1]
        while pickups and pickups[-1] == 0:
            del pickups[-1]
        answer += 2 *(max(len(deliveries),len(pickups)))
        x = cap
        for i in reversed(range(len(deliveries))):
            if x < deliveries[i]: # 더 많이 가지고 있음
                deliveries[i] -= x
                break
            else:
                x -= deliveries[i]
                deliveries[i] = 0
        y = cap
        for i in reversed(range(len(pickups))):
            if y < pickups[i]: # 더 많이 가지고 있음
                pickups[i] -= y
                break
            else:
                y -= pickups[i]
                pickups[i] = 0
    return answer

그리디 알고리즘이다, 같은 인덱스에서 둘 중에 큰값 만큼은 무조건 가야 최선의 방법이다.