[프로그래머스] 택배 배달과 수거하기

---

📌 문제 설명

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

 

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

 

📌 제한 사항

• 1 ≤ cap ≤ 50
• 1 ≤ n ≤ 100,000
• deliveries의 길이 = pickups의 길이 = n
  • deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
  • pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
  • 0 ≤ deliveries의 원소 ≤ 50
  • 0 ≤ pickups의 원소 ≤ 50
• 트럭의 초기 위치는 물류창고입니다.

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

#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 didx = n - 1;
    int pidx = n - 1;
    
    while(didx >= 0 || pidx >= 0){
        while (didx >= 0 && deliveries[didx] == 0) {
            didx--;
        }
        
        while (pidx >= 0 && pickups[pidx] == 0) {
            pidx--;
        }
        
        int distance = max(didx, pidx) + 1;
        answer += distance * 2;

        int capacity = cap;
        
        while (didx >= 0 && capacity > 0) {
            if (deliveries[didx] <= capacity) {
                capacity -= deliveries[didx];
                deliveries[didx] = 0;
                didx--;
            } else {
                deliveries[didx] -= capacity;
                capacity = 0;
            }
        }
        
        capacity = cap;
        while (pidx >= 0 && capacity > 0) {
            if (pickups[pidx] <= capacity) {
                capacity -= pickups[pidx];
                pickups[pidx] = 0;
                pidx--;
            } else {
                pickups[pidx] -= capacity;
                capacity = 0;
            }
        }
    }
    
    return answer;
}

---

📝 풀이

• 가장 먼 집부터 배달과 수거를 고려하기 위하여 didx와 pidx를 n - 1로 초기화합니다.
• 트럭이 가장 먼 위치로 이동 하기 위한 거리를 계산합니다.
• 가장 먼 거리의 집을 왕복한 거리를 추가합니다.
• cap을 초과하지 않는 범위에서 배달 작업을 수행합니다.
• cap을 초과하지 않는 범위에서 수거 작업을 수행합니다.