[Algorithm] Programmers :: 택배 배달과 수거하기

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

프로그래머스

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups)
{
    long long answer = 0;
 
    int deliveryMaxIndex = -1;
    int pickupMaxIndex = -1;
 
    for (int i = n - 1; i >= 0; --i)
    {
        if (deliveries[i] > 0)
        {
            deliveryMaxIndex = i;
            break;
        }
    }
 
    for (int i = n - 1; i >= 0; --i)
    {
        if (pickups[i] > 0)
        {
            pickupMaxIndex = i;
            break;
        }
    }
 
    while (1)
    {
        // 배달 후, 수거
 
        int maxDistanceIndex = max(deliveryMaxIndex, pickupMaxIndex);
 
        answer += (maxDistanceIndex + 1) * 2;
        int curBoxCount = cap;
        int curCap = cap;
 
        for (int i = deliveryMaxIndex; i >= 0; --i) 
        {
            int gap = curBoxCount - deliveries[i];
 
            if (gap >= 0) // 현재집에 전부 배달했으면
            {
                if (i == 0)
                {
                    deliveryMaxIndex = -1;
                }
 
                curBoxCount -= deliveries[i];
                deliveries[i] = 0;
            }
            else // 물건이 부족하면
            {
                deliveries[i] -= curBoxCount;
                deliveryMaxIndex = i; // 다음에 여기부터 시작해야한다는 뜻.
                break;
            }
        }
 
        for (int i = pickupMaxIndex; i >= 0; --i)
        {
            int gap = curCap - pickups[i];
 
            if (gap >= 0)
            {
                if (i == 0)
                {
                    pickupMaxIndex = -1;
                }
                curCap -= pickups[i];
                pickups[i] = 0;
            }
            else
            {
                pickups[i] -= curCap;
                pickupMaxIndex = i;
                break;
            }
        }
 
        if (deliveryMaxIndex == -1 && pickupMaxIndex == -1) break;
    }
 
    return answer;
}

그리디유형이라 생각되는 문제이다.

최소의 움직임으로 모든 택배배달과 수거를 끝내야 한다.

그러기 위해서는 배달과 수거 모두 반드시 끝지점에서부터 처리해야 한다.

 

효율적인 움직임을 위해서 반드시 끝지점까지 갔다가(배달) 다시 물류창고로 되돌아오는(수거) 행동을 하게 되는데, 끝지점부터 해결해야 가야만 하는 끝지점이 점점 줄어들 수 있기 때문이다.

그래서 각 싸이클마다 answer에 가야만하는 집까지의 최대거리 * 2를 누적해준다. (

 

배달의 경우 먼저 실을 수 있는만큼(cap)만큼 실어서 끝지점에 먼저 갔다주고, 그래도 여유분이 있으면 이전집에 할당하는 식이다.

수거 또한 cap만큼 끝집부터 수거하면서 여유가 되면 이전집을 탐색하게 되는데, cap만큼이 보장되는 이유는 수거하기 전에는 반드시 트럭이 비어있다고 보장되기 때문이다. 애초에 필요한만큼만 배달이 수행되기 때문이다.

 

배달이든 수거든, 끝지점부터 0번째로 탐색하면서 cap으로 부족할 경우, 해당 지점을 다음 싸이클때 시작지점으로 저장하고 현재 싸이클을 그만둔다.

현재 싸이클을 그만뒀는데 각각의 시작지점이 -1, 즉 배달과 수거 모두 첫번째집까지 마쳤을 경우 반복문을 아예 탈출한다.