[카카오블라인드] 택배 배달과 수거하기

문제 설명

택배차의 창고 크기가 한정되어 있어 어떤 순서로 택배를 배달하고, 수거하면 택배 차의 움직임을 최소로 할 수 있을까? 

 

아이디어 

주어진 조건이 아래의 그림과 같을 때,  택배차가 최소로 움직이는 경로는 

1. #4, 5번 집에 택배를 배달하고 돌아오는 길에 #4집의 택배를 수거

2. 그 후 창고로 돌아와 다시 #1,3 번 집에 택배를 배달하고 #2번 집의 택배를 수거

3. 총 16번의 움직임으로 해결할 수 있다.

 

---

*여기서 부터 설명은 아래 그림 기준으로 설명함*

 

여기서 중요한 아이디어는 창고에서 출발할 때는 풀 CAP으로 적재하고, 배달이나 수거하하는 순서를 멀리있는 집을 기준으로 삼아야 한다. 

 

항상 택배차 용량만큼 적재해야 하는 이유는 수거해야 하는 집(집 #5)이 배달해야하는 집(집 #4)보다 더 멀리 있어도 배달을 하면서 해당 집에 도착할 때 항상 택배차 용량을 0으로 만들 수 있기 때문이다. 

 

왜 항상 택배차 용량을 0으로 만들 수 있냐면 집 #3, 4에서 택배를 내려두고 #5로 출발하면 되기 때문이다.

 

그럼 항상 마지막 집부터 배달, 수거를 진행하는 이유는 거리가 하나씩 줄어들기 때문이다.

만약 집 #3에 있는 택배부터 배달을 완료했다고 가정하면, 집#4를 갈 때 집 #3을 지나가야 하는 쓸모없는 움직임이 존재하기 때문이다.

 

즉 우리는 

1. 창고에서 출발할 때는 항상 택배차 용량을 가득 적재한다. 단 배달해야 하는 택배가 택배차 용량보다 적다면 배달해야 하는 택배 만큼만 적재한다.

2. 먼 곳부터 배달하고, 수거해야 한다.

3. 움직인 거리는 배달, 수거가 남은 집 중 제일 먼집의 거리 * 2를 해주면 된다. 

 

이러한 조건으로 최대 용량이 4인 택배차를 이용한다고 가정하면 

1. 집 #3에 방문해 두 개 배달

2. 집 #4에 방문해 두 개 배달 

3. 집 #5에 방문해 전부 수거

4. 여기서 #5가 제일 먼 집임으로 택배차 움직임은 10이다.

코드

def caculate_spend_day(deliveries, cap):
    needed_day = [0] * len(deliveries)
    n = len(deliveries)
    max_cap = cap
    day = 1

    site_idx = n - 1
    
    while 0 <= site_idx:
        if deliveries[site_idx] == 0:
            site_idx -= 1
            continue

        #이번 장소에 있는 물건은 충분히 다을 수 있음
        if deliveries[site_idx] <= cap:
            cap -= deliveries[site_idx]
            deliveries[site_idx] = 0
            needed_day[site_idx] = day

        #이번 장소에 있는 물건 중 일부만 담을 수 없음
        else:
            deliveries[site_idx] = deliveries[site_idx] - cap #당믈 수 있는 만큼 담아서 출발
            day += 1                           
            cap = max_cap
    
    return needed_day

def calculated_move(result, n):
    answer = 0
    spended_day = 0

    for i in range(n, 0, -1):
        day = result[i] - spended_day

        if day <= 0:
            continue

        spended_day += day
        answer += day * (i * 2)

    return answer

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

    deliveries.insert(0, 0)
    pickups.insert(0, 0)

    calc_delivers = caculate_spend_day(deliveries, cap)
    calc_pickups = caculate_spend_day(pickups, cap)

    result = []

    for i in range(len(calc_delivers)):
        result.append(max(calc_delivers[i], calc_pickups[i]))    

    answer = calculated_move(result, n)
    return answer

if __name__ == "__main__":
    cap = 4	
    n = 6	
    deliveries =[1, 0, 3, 1, 2, 0]
    pickups = [0, 3, 0, 4, 0, 1]	
    result = 16

    print(solution(cap, n, deliveries, pickups))