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

프로그래머스

 

1. 문제

트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다.

각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

 

[입력]

1. cap: 트럭에 실을 수 있는 재활용 택배 상자의 최대 개수
2. n: 배달할 집의 개수
3. deliveries: 각 집에 배달할 재활용 택배 상자의 개수
4. pickups: 각 집에서 수거할 빈 재활용 택배 상자의 개수

 

[출력]

트럭 하나로 모든 배달과 수러를 마치고 물류 창고까지 돌아올 수 있는 최소 이동 거리를 return

 

2. 풀이

어렵게 생각하지 않고 간단하게 생각해보면 쉽게 풀 수 있는 문제였습니다.ㅎㅎ 😭

가장 먼 집에서 부터 시작해, 배달할 수 있을만큼 전부 배달하고 픽업할 수 있을만큼 전부 픽업해오면 됩니다.

 

👇🏻 요렇게

 

이를 코드로 구현하면 아래와 같습니다.

# 실을 수 있는 수
delivable = cap

while deliver >= 0:
	# 모든 택배를 배달할 수 있는 경우
    if delivable - deliveries[deliver] >= 0:
    	delivable -= deliveries[deliver]
        deliver -= 1
    # 일 부분만 배달할 수 있는 경우
    else:
    	# 일부분의 택배만 배달
        deliveries[deliver] -= deliverable​

 

이는 택배를 회수할 때도 동일합니다. 🤗👍🏻

트럭이 한 번 이동할 때 택배를 배달하는 동작과 회수하는 동작을 함께 수행하게 됩니다.

그렇다면 택배를 배달해야 하는 가장 먼 집과 택배를 회수해야 하는 가장 먼 집 중 더 먼 거리가 해당 회차 때 실질적으로 이동해야 하는 거리임을 알 수 있습니다.

위와 같은 상황일 경우, 실질적으로 이동해야 하는 거리는 더 멀리 이동해야 하는 5입니다.

 

3. 코드

def solution(cap, n, deliveries, pickups):
    answer = 0
    
    # 뒤에서 부터 탐색
    deliver, pickup = n-1, n-1
    
    while deliver >= 0 and deliveries[deliver] == 0: deliver-=1
    while pickup >= 0 and pickups[pickup] == 0: pickup-=1
    
    while deliver >= 0 or pickup >= 0:
        answer += (max(deliver, pickup)+1) * 2
        delivable, pickable = cap, cap
        
        while deliver >= 0:
            if delivable - deliveries[deliver] >= 0:
                delivable -= deliveries[deliver]
                deliver -= 1
            else:
                deliveries[deliver] -= delivable
                break
            
        while pickup >= 0:
            if pickable - pickups[pickup] >= 0:
                pickable -= pickups[pickup]
                pickup -= 1
            else:
                pickups[pickup] -= pickable
                break
        
    return answer