문제 - 택배 배달과 수거

접근 방법

처음보고 그리디 알고리즘을 사용해야된다는 건 알았다. 그래서 처음 설계를 할 때에 가장 먼거리의 집부터 택배 배달을 시작하고 돌아오면서 최대용량만큼의 빈 상자를 수거한다.
가장 먼거리의 집에 가서 용량이 꽉차면 바로 수거하러 가지만 꽉차지않으면 그 이전의 집에 남은 용량만큼의 택배를 수거한다.
그리고 거리를 계산할 때에는 왕복거리로 계산한다고 생각을 했지만 구현을 하려고하니 머리가 복잡해졌다.
그래서 밑의 자료를 참고해서 잉여량은 이전의 집으로 보내서 같이 계산을 하는 방법으로 구현을 했다.
만약 마지막의 집에는 배달할 상자가 5개가 있지만 최대용량이 4개이면 1개가 남게 된다 그러면 다시 재방문을 해야되므로 방문횟수를 늘려준다.

참고자료

나중에 다시한번 풀어봐야되겠다..

소스코드

import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int now_deliver = 0, now_pickup = 0;
        
        //가장 먼거리의 집부터 탐색
        for(int i=n-1;i > -1; i--)
        {
            //방문횟수
            int num = 0;
            deliveries[i] += now_deliver;
            pickups[i] += now_pickup;
            
            //해당 집에서 잉여량이 있다면 재방문
            while(deliveries[i] > 0 || pickups[i] > 0)
            {
                deliveries[i] -= cap;
                pickups[i] -= cap;
                num++;
            }
            
            now_deliver = deliveries[i];
            now_pickup = pickups[i];
            
            answer = answer + (i+1) * 2 * num;
        }
        return answer;
    }
}