택배 배달과 수거하기 [Lv.2]

프로그래머스

 

일렬로 나열된 N개의 집에 택배를 배달, 수거할 때 최소 비용을 구하는 문제입니다.

택배 트럭은 한번에 cap개만 실을 수 있습니다.

 

풀이 방법

i번째 집에 한번 방문하면 무조건 i * 2의 비용이 발생합니다.

이때 트럭 공간이 모자라 수거, 배달을 전부 못했다면 i번째 집에 다시 방문할 것이고

트럭 공간이 여유가 있다면 다음 집(i - 1)에도 방문하여 수거, 배달을 할 수 있을 것 입니다.

 

즉 문제 풀이법의 핵심은 재방문 여부와 여유 공간의 유무 확인에 있습니다.

 

정답 코드

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    
    int d = 0;
    int p = 0;
    
    for (int i = n - 1; i >= 0; i--)
    {
        d -= deliveries[i];
        p -= pickups[i];
        int cnt = 0;
        
        while (d < 0 || p < 0){
            d += cap;
            p += cap;
            cnt++;
        }
        answer += (i + 1) * 2 * cnt;
    }
    return answer;
}