문제

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.

배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)

트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

풀이

항상 가장 멀리 있는 집부터 가야하는 그리드 알고리즘이다.

가장 먼 집부터 가까운 집 순서로 for문을 돌며 각 집의 배달과 수거를 하는데
해당 위치에 배달, 수거 둘 중 하나가 가능하다면(0보다 크다면) while문을 돌며 배달, 수거가 끝날때 까지 반복한다.
이때 항상 cap만큼 반복하기 때문에 음수가 될 수 있다. 음수가 되는 부분은 다음 순서의 집에서 해야할 작업을 미리 한 것이라 생각해도 문제가 없다.
따라서 0보다 크지 않은 작업들은 다음 순서의 집에 이월시킨 후 다시 반복한다.

처음에는 조건문을 여러개 써가며 상자의 개수에 맞게 배달, 수거하도록 작성하였는데 쓸데 없이 길어지고 복잡해지기만 할 뿐이였다.
음수가 되는 부분을 어짜피 처리해야 할 상자들이므로 음수만큼을 다음 순서에 더해 처리하는 방법이 훨씬 깔끔하게 풀렸다.

코드

#include <string>
#include <vector>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    
    int pre_deli = 0;
    int pre_pick = 0;
    for (int i = n-1; i > -1; i--){
        int count = 0;
        
        deliveries[i] += pre_deli;
        pickups[i] += pre_pick;
        while (deliveries[i] > 0 || pickups[i] > 0){
            deliveries[i] -= cap;
            pickups[i] -= cap;

            count++;
        }
        pre_deli = deliveries[i];
        pre_pick = pickups[i];
        
        answer += count * (i+1) * 2;
    }

    return answer;
}