[150369] 택배 배달과 수거하기

✔ 택배 배달과 수거하기

[프로그래머스 150369]

문제 분석하기

가장 멀리 있는 집부터 택배를 배달하도록 하며 이때 이 집에 몇 번 트럭이 오게 되는지 카운트하도록 함

 

예) cap = 4, deliveries = [1, 0, 3, 1, 2], pickups = [0, 3, 0, 4, 0]

i	deliver	pickup	count	answer
5번째 집	2 → 2 - 4 = -2이므로 1번 방문 해야 함	0 → 0 - 4 = -4이므로 1번 방문해야 함	1번	5 * 1 * 2 = 10 0 + 10 = 10
4번째 집	-2 → -2 + 1 = -1이므로 5번째 집 배달을 가면서 배달 가능	-4 → -4 + 4 = 0이므로 5번째 집에서 돌아오면서 수거 가능	0번	10
3번째 집	-1 → -1 + 3 = 2 → 2 - 4 = -2이므로 1번 방문해야 함	0 → 0 + 0 = 0 → 0 - 4 = -4	1번	3 * 1 * 2 = 6 10 + 6 = 16
2번째 집	-2 → -2 + 0	-4 → -4 + 3 = -1이므로 3번째 집에서 돌아오면서 수거 가능	0번	16
1번째 집	-2 → -2 + 1 = -1이므로 3번째 집 배달을 가면서 배달 가능	-1 → -1 + 0 = -1	0번	16

손으로 풀어보기

1. 가장 멀리 있는 집부터 택배를 배달
2. 가장 멀리 있는 집의 택배와 재활용 택배 상자를 모두 없애기 위해 몇 번을 방문해야하는지 횟수 카운트
3. 횟수에 대해 거리 계산을 하여 최소 이동 거리에 합하도록 함

슈도코드 작성하기

cap(트럭에 실을 수 있는 재활용 택배 상자의 최대 개수)
n(배달할 집의 개수)
deliveries(각 집에 배달할 재활용 택배 상자의 개수)
pickups(각 집에서 수거할 빈 재활용 택배 상자의 개수)
answer(트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리)
deliver(배달할 택배 상자 개수)
pickup(수거할 재활용 택배 상자 개수)
for(i -> n - 1부터 0까지) {
    count(현재 집 방문 횟수)
    deliver를 deliveries[i]만큼 증가
    pickup을 pickups[i]만큼 증가
    while(한 집에 대해서 택배를 모두 배달하고 재활용을 모두 수거할 동안) {
        count 증가
        cap만큼 deliver, pickup 감소
    }
    (i + 1) * count * 2의 거리만큼 answer 증가
}
answer 반환

코드 구현하기

/**
 * 150369) 택배_배달과_수거하기
 */
public class L092_150369 {
    // cap(트럭에 실을 수 있는 재활용 택배 상자의 최대 개수)
    // n(배달할 집의 개수)
    // deliveries(각 집에 배달할 재활용 택배 상자의 개수)
    // pickups(각 집에서 수거할 빈 재활용 택배 상자의 개수)
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        // answer(트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리)
        long answer = 0;
        // deliver(배달할 택배 상자 개수)
        int deliver = 0;
        // pickup(수거할 재활용 택배 상자 개수)
        int pickup = 0;
        // 가장 먼 집부터
        for (int i = n - 1; i >= 0; i--) {
            // count(현재 집 방문 횟수)
            int count = 0;
            // 현재 집에서 배달할 택배 상자와 수거할 재활용 택배 상자 개수만큼 증가
            deliver += deliveries[i];
            pickup += pickups[i];
            // 한 집에 대해서 택배를 모두 배달하고 재활용을 모두 수거할 동안
            while (deliver > 0 || pickup > 0) {
                // count 증가
                count++;
                // cap만큼 deliver, pickup 감소
                deliver -= cap;
                pickup -= cap;
            }
            // (i + 1) * count * 2의 거리만큼 answer 증가
            answer += (i + 1) * count * 2;
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L092_150369 solution = new L092_150369();

        int cap = 4;
        int n = 5;
        int[] deliveries = { 1, 0, 3, 1, 2 };
        int[] pickups = { 0, 3, 0, 4, 0 };

        long result = solution.solution(cap, n, deliveries, pickups);

        System.out.println(result);
    }
}