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

 

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

 

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

프로그래머스

---

 

 

해결전략

 

그리디 알고리즘 Greedy Algorithm  탐욕법

 

---

 

 

처음 시도한 코드

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

long long solution(int cap, int n, vector<int> dv, vector<int> pickups) {
    long long answer = 0;

    int i = n - 1;
    while(i)
    {
        bool bVisit = false;
        int box = cap;

        // 배달
        while (i) 
        {
            if (dv[i] == 0){
                i--;
                continue;
            }

            if (false == bVisit){
                bVisit = true;
                answer += (i + 1) * 2; // 현재 집까지 이동 + 택배창고까지 되돌아감.
            }

            if (box >= dv[i]){ // 배달 완료.
                box -= dv[i];
                dv[i] = 0;
                i--;
            }
            else { // 배달 미완료. box < dv[i]
                box = 0;
                dv[i] -= box;
                break;
            }
        }

        
        int recycle = cap; // 재활용 수거

        // 배달을 완료한 집부터 재활용 수거
        for (int j = i; j >= 0; j--)
        {
            if (pickups[j] == 0) continue;

            if (cap > recycle){
                if (cap - recycle >= pickups[j]){
                    recycle += pickups[j];
                    pickups[j] = 0;	                
                }
                else if (cap - recycle < pickups[j]){
                    recycle += (cap - recycle);
                    pickups[j] -= (cap - recycle);
                }
            }

            if (recycle == cap) break;
        }

    }

    return answer;
}

 

---

 

 

정답 코드

 

#include <string>
#include <vector>
using namespace std;

long long solution(int cap, int n, vector<int> dv, vector<int> pickups) {
    long long answer = 0; // 총 이동 거리

    int i = n - 1; // 마지막 집부터 시작
    while (i >= 0) // 모든 집을 방문할 때까지 반복
    {
        // 현재 집에서 배달 및 수거할 것이 없으면 다음 집으로 이동
        while (i >= 0 && dv[i] == 0 && pickups[i] == 0) {
            i--;
        }

        if (i < 0) break;  // 더 이상 배달 및 수거할 것이 없으면 루프 종료

        answer += (i + 1) * 2; // 현재 집까지 이동 + 택배 창고까지 되돌아감

        int box = cap; // 현재 트럭의 최대 적재량을 저장하는 변수

        // 배달을 수행하는 루프
        for (int j = i; j >= 0; j--) 
        {
            if (dv[j] > 0) {
                int deliverable = min(dv[j], box); // 현재 트럭에 실을 수 있는 최대 배달량
                dv[j] -= deliverable; // 배달 후 남은 물량
                box -= deliverable; // 트럭의 남은 용량
            }

            if (box == 0) break; // 트럭이 꽉 차면 루프 종료
        }

        int recycle = cap; // 재활용품을 수거하기 위한 트럭의 최대 적재량

        // 재활용 수거를 수행하는 루프
        for (int j = i; j >= 0; j--) 
        {
            if (pickups[j] > 0) {
                int pickupable = min(pickups[j], recycle); // 현재 트럭에 실을 수 있는 최대 수거량
                pickups[j] -= pickupable; // 수거 후 남은 물량
                recycle -= pickupable; // 트럭의 남은 용량
            }

            if (recycle == 0) break; // 트럭이 꽉 차면 루프 종료
        }

        // 배달 및 수거가 완료되었으므로 다음 집으로 이동
        while (i >= 0 && dv[i] == 0 && pickups[i] == 0) {
            i--; // 배달과 수거가 모두 완료된 집은 건너뜀
        }
    }

    return answer; 
}

 

 

---