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

문제

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

풀이

1. 배달할 물건이나, 회수할 물건이 i번째까지 존재한다면, i번째까지 적어도 한 번은 가야함
2. 한 번 출발하여 물류창고로 돌아오면, cap 만큼의 배달을 수행 할 수 있고 cap 만틈의 물건을 회수 할 수 있음
3. 한 곳에서 택배를 전부 배달하지 못했거나 회수하지 못했다면, 물류창고로 돌아왔다가 다시 같은 장소로 떠나야 함

트럭이 한 번 떠나면 cap만큼의 물건을 배달할 수 있고, cap만큼의 물건을 회수할 수 있음
배열 거꾸로 탐색하기 !

문제의 조건을 단순화 하니까 이렇게 간단하게 풀릴 줄이야...? 저 풀이 방법 천재같다...

코드

#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 d = 0, p = 0;
    
    for(int i=n-1; i>=0; i--) {
        int cnt = 0; //트럭 왔다갔다 이동 횟수
        d -= deliveries[i];
        p -= pickups[i];
        
        while(d < 0 || p < 0) {
            d += cap; //전달 할 물건 존재했기에 cap만큼의 배달량을 처리 할 수 있음
            p += cap; //회수 할 물건 존재했기에 cap만큼의 회수량을 처리 할 수 있음
            cnt += 1; //해당 장소에 한 번 방문한 것으로 커버되지 않으면, 다시 방문해서 cap만큼의 배달량, 회수량 즐가시킴
        }
        
        answer += (i+1) * 2 * cnt; //여기서 cnt 곱해줘야 함!
    }

    return answer;
}