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

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

문제 분석 및 접근 방식

이 문제는 여러 집에 택배를 배달하고, 동시에 빈 재활용 상자를 수거해야 하는 상황에서 최소한의 이동 거리로 모든 작업을 완료하는 최적화 문제입니다. 트럭에는 재활용 택배 상자를 최대 cap 개까지 실을 수 있으며, 각 집마다 배달할 상자와 수거할 빈 상자의 개수가 주어집니다.

문제에서 요구하는 것은 다음과 같습니다:

1. 각 집에 필요한 택배 상자를 배달하고 빈 상자를 수거하는 작업을 최소한의 이동 거리로 완료해야 합니다.
2. 트럭은 물류창고를 출발해 가장 먼 집까지 이동하면서 배달과 수거를 동시에 처리하고, 다시 물류창고로 돌아옵니다.

뒤에서 부터 탐색을 한다면?

• 스택을 이용한 거꾸로 탐색:
  • 집의 위치를 고려할 때, 가장 먼 집부터 가까운 집으로 거슬러 올라가며 배달과 수거 작업을 수행합니다.
  • 스택을 사용하여 각 집의 배달할 상자와 수거할 빈 상자 개수를 저장합니다. 이렇게 하면 가장 먼 집부터 처리할 수 있습니다.
• 최대 거리 계산:
  • 매번 배달 또는 수거 작업을 할 때, 현재 처리하는 집까지의 거리를 계산하여 왕복 거리를 구합니다. 이 거리를 누적하여 최종적으로 최소 이동 거리를 계산합니다.
  • 배달 작업과 수거 작업은 동시에 이루어지기 때문에, 두 작업 중 더 먼 집까지의 거리를 기준으로 왕복 거리를 계산합니다.
• 트럭의 용량을 고려한 작업 분배:
  • 트럭의 최대 용량 cap을 초과하지 않도록 배달할 상자와 수거할 상자를 적절히 분배합니다.
  • 트럭의 용량이 초과되면, 남은 작업은 다음 반복에서 처리하게 됩니다.

#include <bits/stdc++.h>
using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    stack<int> D, P; 
    
    for(auto i : deliveries) D.push(i); // 배달할 택배 상자를 스택에 추가
    for(auto i : pickups) P.push(i); // 수거할 빈 상자를 스택에 추가
    
    // 스택의 최상단에 있는 0 값을 제거
    while(!D.empty() && D.top() == 0) D.pop();
    while(!P.empty() && P.top() == 0) P.pop();
    
    // 배달 및 수거 작업이 끝날 때까지 반복
    while(!(D.empty() && P.empty())) {
        int box = 0;
        answer += max(D.size(), P.size()) * 2; // 가장 먼 거리만큼 왕복
        
        // 배달 작업
        while(!D.empty() && box <= cap) {
            if(D.top() + box <= cap){
                box += D.top();
                D.pop();
            } else {
                D.top() -= (cap - box);
                break;
            }
        }
        
        box = 0;
        
        // 수거 작업
        while(!P.empty() && box <= cap) {
            if(P.top() + box <= cap){
                box += P.top();
                P.pop();
            } else {
                P.top() -= (cap - box);
                break;
            }
        }
    }
    
    return answer;
}