[Programmers] 택배 배달과 수거하기 (Java)

🛠️ 문제 🛠️

1. 당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다.
   → deliveries 의 길이 = pickups의 길이 = n
2. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
3. 배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
4. 트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다.
5. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다.
   → 배달하거나 수거할 가장 먼 집 i → 물류창고와 i를 왕복해야한다.
6. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 
   → 가장 먼 곳의 작업을 먼저 완료해야한다.
7. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.
   → 한 집에 여러번 방문할 수 있다.

---

🗒️ 설명 🗒️

처음 이 문제를 읽고 가장 먼저 떠올린 방법은 현재 남아있는 작업 중 가장 먼 집의 인덱스를 저장하며 배열을 변경해 나아가는 것이었다.

하지만 반복문 속 반복문이 계속 생겨 시간복잡도도 커지고 구현할 수록 경우의 수가 늘어나서 구현하기 어려웠다.

그래서 다른 사람의 풀이를 조금 참고했는데 정말 간단하고 생각을 좀 전환하는 계기가 되어 기록을 남겨둔다.

 

우선 나는 한번 왕복할 때의 상태를 배열에 무조건 변경을 하려고 했다.

하지만 문제를 좀 더 생각해보면

- 배달해야할 택배와 수거해야할 택배의 개수는 정해져 있다.
- 한번 배달하러 간 후 돌아올 때 트럭의 용량의 다시 원점으로 돌아간다.
   즉, 회수하러 출발할 때 트럭은 비어있다.
- 트럭이 모든 택배를 배달하러 가는 동안 최대로 실을 수 있는 양은 cap x (출발한 횟수)
   반대로 물류창고로 모두 회수하는 동안 최대로 실을 수 있는 양 또한 cap x (도착한 횟수) 이다.

 

내가 이해한 내용을 토대로 그림을 그려보면 아래와 같다.

즉, 최소 이동 거리를 구하려면 왕복횟수를 줄여야한다.

왕복 횟수를 줄이려면 트럭 용량을 꽉 채워서 택배를 배달하고 수거해야한다.

물류창고로부터 가장 멀리 떨어져 있는 집의 작업처리를 우선으로 하되 가는 동안에 처리할 수 있는 작업이 있을 것이다.

위의 그림에서 보면 5번 집의 작업을 처리하기 위해 한번 왕복하면 가는 동안 2개, 오는 동안 4개의 상자를 더 처리할 수 있어 4번 집 작업을 같이 처리하고 3번 집의 배달 1개를 처리한다.

→ 이렇게 하면 5번 집을 왕복하는데 최대로 해결할 수 있는 작업을 처리한다.

이와 같은 방식으로 최소 이동거리를 구할 수 있다.

 

내가 이 문제를 풀면서 느낀 것은 현재 나는 문제를 너무 있는 그대로만 생각한다.

문제에서 나타내는 문장이 의미하는 것까지 생각을 못하고 있었다.

 

그래서 이번 문제를 풀면서 그 문장이 어떤 의미를 가지고 있는지, 그 의미를 이용하여 문제를 좀 더 단순하게 풀어본 시간이었다.

앞으로 문제를 빠르게 읽는 것도 중요하지만 그 의미를 파악하는 시간을 가지도록 해야겠다.

---

🍀 풀이 🍀

/**
 * 택배 배달과 수거하기
 * https://school.programmers.co.kr/learn/courses/30/lessons/150369
 */
public class Parcel {
    public static void main(String[] args) {
        int cap = 4;
        int n = 5;
        int[] deliveries = {1, 0, 3, 1, 2};
        int[] pickups = {0, 3, 0, 4, 0};
        System.out.println(solution(cap, n, deliveries, pickups));
    }

    /**
     * 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리
     * @param cap 트럭 용량
     * @param n 배달할 집의 개수
     * @param deliveries 각 집에 배달할 택배 상자의 개수
     * @param pickups 각 집에서 수거할 상자 개수
     * @return 최소 이동 거리
     */
    public static long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int d = 0; // 가는 동안 배달할 수 있는 택배 용량 
        int p = 0; // 오는 동안 수거할 수 있는 택배 용량
        for(int i = n-1; i >= 0; i--) { //물류창고에서 가장 먼 곳의 작업부터 처리!
            //현재 택배를 트럭에 담는다.
            d -= deliveries[i];
            p -= pickups[i];

            // 가거나 오는 차량의 용량이 부족할 경우
            while(d < 0 || p < 0) {
                // 이동하는 동안 옮길 수 있는 용량 추가
                d += cap;
                p += cap;
                answer += (i+1) * 2; // 물류창고에서 (i+1)번째 집까지 이동거리
            }
        }
        return answer;
    }
}