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

Problem

https://school.programmers.co.kr/learn/courses/30/lessons/150369?language=java
당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

Solution

• 한 번에 갈 수 있는 최대 거리부터 계산하기 위해 맨 끝 집부터 탐색한다.
• 맨 끝 집에서 배달해야할 상자와 픽업해야하는 상자의 개수를 sumDel, sumPick에 더한 뒤 둘 다 0보다 작은 값이 될 때까지 cap을 더해준다. cap을 더해주는 이유는 한 집에 배달 가능한 택배와 수거 가능한 택배의 최댓값이 cap이기 때문이다.
• cap을 더해준 횟수가 해당 집의 방문횟수가 되고 방문할 때마다 이동거리는 (i + 1) * 2 * cnt가 된다. i + 1을 하는 이유는 인덱스는 0부터 시작하지만 거리는 1부터 시작하기 때문이다.
• 해당 집에 택배 배달 및 수거를 완료했다면 앞 집으로 이동하고 앞 집에서도 배달과 수거를 반복한다.
• 맨 앞 집까지 모두 탐색한 뒤 각 이동거리를 모두 더하면 이동거리 최솟값을 구할 수 있다.

JAVA Code

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int sumDel = 0;
        int sumPick = 0;
       
        for (int i = n - 1; i >= 0; i--) {
            int cnt = 0;
            sumDel += deliveries[i];
            sumPick += pickups[i];
            
            while (sumDel > 0 || sumPick > 0) {
                sumDel -= cap;
                sumPick -= cap;
                cnt++;
            }
            answer += (i + 1) * 2 * cnt;
        }
        return answer;
    }
}