프로그래머스 택배 배달과 수거하기 - C++ 풀이

---

 

1. 배달은 갈 때, 수거는 돌아올 때 한다.
2. 최대한 먼 집부터 해결하는 것이 최적이다.
3. 배달할 상자와 수거할 상자가 모두 없어질 때까지 반복한다.

 

1. 배달은 갈 때, 수거는 돌아올 때 한다.

 이동 거리를 최소화해야 한다. 물류센터에서 출발할 때 트럭을 배달상자로 가득 채우고 출발한다. 가면서 각 집에 상자를 배달하여 트럭을 비우고, 다시 물류센터로 돌아오면서 수거상자들로 트럭을 채워오자.

 

2. 최대한 먼 집부터 해결하는 것이 최적이다.

 또한 이동 거리를 최소화하기 위해서는 최대한 먼 집부터 방문하는 것이 최적이다. (A<B이면, B로 가는 길에 A를 무조건 거치기 때문에 남는 용량으로 A에 대한 배달/수거도 같이 진행할 수 있다. 하지만 반대는 불가능하다.) 

 

3. 배달할 상자와 수거할 상자가 모두 없어질 때까지 반복한다.

 배달할 상자와 수거할 상자가 모두 없어질 때까지 배달&수거를 반복한다. 주의할 사항은 배달하지 않고 남은 상자가 있다면 그냥 버려서 트럭을 비워야 돌아오는 길에 수거 상자를 최대한으로 담을 수 있다는 것이다. (남은 배달상자를 버리는 것은 출발할 때 필요한 개수 만큼의 배달상자만 담아 출발한 것과 같으므로 문제가 되지 않는다.)

---

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    
    int dp = n-1;   // 배달할 거리가 남아있는 집 중 가장 먼 곳
    int pp = n-1;   // 수거할 거리가 남아있는 집 중 가장 먼 곳
    int truck = cap;  // 트럭에 실린 물건 수
    
    while (dp >= 0 || pp >= 0) {
        int dist = 0;
        
        // 트럭을 배달상자로 채움
        truck = cap;
        
        // 배달은 갈 때
        while (truck > 0 && dp >= 0) {
            // 배달
            int amount = min(truck, deliveries[dp]);
            deliveries[dp] -= amount;
            truck -= amount;
            
            // 가장 먼 곳 업데이트
            if (amount != 0) dist = max(dist, dp+1);
            
            // dp번 집에 모든 배달을 완료한 경우 포인터 업데이트
            if (deliveries[dp] == 0) dp--;
        }
        
        // 배달할 곳이 없는 경우 트럭 비우고 출발
        if (dp == -1) truck = 0;
        
        // 수거는 올 때
        while (truck < cap && pp >= 0) {
            // 수거
            int amount = min(cap - truck, pickups[pp]);
            pickups[pp] -= amount;
            truck += amount;
            
            // 가장 먼 곳 업데이트
            if (amount != 0) dist = max(dist, pp+1);
    
            // pp번 집에서 모든 수거를 완료한 경우 포인터 업데이트
            if (pickups[pp] == 0) pp--;
        }
        
        // 물류창고로 돌아옴
        answer += dist * 2;
    }
    
    return answer;
}