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

 최소 이동거리를 구하는 것이 문제이기 때문에 그리디, BFS, DFS 정도를 생각해 볼 수 있다.

 

각 집들이 일렬로 연결되어 있고 모든 거리가 1이기 때문에 그리디 알고리즘을 사용해야한다.

 

그렇다면 어떤 방식으로 그리디 알고리즘을 사용해야할까?? 

 

** 배달과 수거를 나눠야한다 **

 

 

배달 거리를 최소화 하는 방법

1. 가장 먼 집을 한번만 탐색하는 방식으로 이동해야 한다.

2. 가장 먼 집을 한번만 탐색하면서 물류창고에서 최대양의 택배를 가져와 최대한 많은 집에 택배를 배달해야한다.

 

위 두가지 조건을 따르려면 물류창고에서 최대 개수의 택배를 가져온 뒤 맨 뒷집부터 차례대로 배달하는것이다.

 

 

    int truck_start = cap;
    int truck_end = 0;
        
    for(int i=dis; i>=0; i--) {
        if(deliveries[i] > truck_start) {
                   deliveries[i] = deliveries[i] - truck_start;                                                            
                truck_start = 0;
            }
            else {
                truck_start -= deliveries[i];
                deliveries[i] = 0;
            }
            if(truck_start == 0) {break;}
        }

 

 

수거 거리를 최소화 하는 방법

1. 가장 먼 집을 한번만 탐색하는 방식으로 이동해야 한다.

2. 가장 먼 집을 한번만 탐색하면서 가장 먼 집에서부터 가져올 수 있는 최대의 수거 박스를 가져와야한다.

 

 

        for(int i=dis; i>=0; i--) {
            int store = cap - truck_end;
            
            if(store > pickups[i]) {
                truck_end += pickups[i];
                pickups[i] = 0;
            }
            else {                                                                                                                    
                pickups[i] = pickups[i] - store;
                truck_end = cap;
            } 
            if(truck_end == cap) {break;}
        }

 

 

 

 

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
 
// 트럭을 두개로 생각해보자
 
long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {                                                        
    long long answer = -1;
    long long result = 0;
    
    // 현재 위치
    int dis = deliveries.size()-1;
    
    while(dis != -1) {
        int truck_start = cap;
        int truck_end = 0;
        
        for(int i=dis; i>=0; i--) {
            if(deliveries[i] > truck_start) {
                deliveries[i] = deliveries[i] - truck_start;
                truck_start = 0;
            }
            else {
                truck_start -= deliveries[i];
                deliveries[i] = 0;
            }
            if(truck_start == 0) {break;}
        }
        
        for(int i=dis; i>=0; i--) {
            int store = cap - truck_end;
            
            if(store > pickups[i]) {
                truck_end += pickups[i];
                pickups[i] = 0;
            }
            else {
                pickups[i] = pickups[i] - store;
                truck_end = cap;
            } 
            if(truck_end == cap) {break;}
        }
        
        if(!(truck_start == cap && truck_end == 0)) {
            result = result + (dis+1) * 2;
        }
        
        for(int i=dis; i>=0; i--) {
            if(deliveries[i] == 0 && pickups[i] == 0) { dis--; }
            else { break; }
        }
    }
    
    answer = result;
    
    return answer;
}