(2023 KAKAO BLIND RECRUITMENT) 택배 배달과 수거하기

문제 설명

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.

배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)

트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

 

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

 

배달 및 수거할 재활용 택배 상자 개수

	집 #1	집 #2	집 #3	집 #4	집 #5
배달	1 개	0 개	3 개	1 개	2 개
수거	0 개	3 개	0 개	4 개	0 개

 

배달 및 수거 과정

	집 #1	집 #2	집 #3	집 #4	집 #5	설명
남은 배달/수거	1/0	0/3	3/0	1/4	2/0	물류창고에서 택배 3개를 트럭에 실어 출발합니다.
남은 배달/수거	1/0	0/3	3/0	0/4	0/0	물류창고에서 5번째 집까지 이동하면서(거리 5) 4번째 집에 택배 1개를 배달하고, 5번째 집에 택배 2개를 배달합니다.
남은 배달/수거	1/0	0/3	3/0	0/0	0/0	5번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 4개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 4개를 트럭에 싣습니다.
남은 배달/수거	0/0	0/3	0/0	0/0	0/0	물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 3개를 배달합니다.
남은 배달/수거	0/0	0/0	0/0	0/0	0/0	3번째 집에서 물류창고까지 이동하면서(거리 3) 2번째 집에서 빈 택배 상자 3개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다.

 

16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.

 

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

• 1 ≤ cap ≤ 50
• 1 ≤ n ≤ 100,000
• deliveries의 길이 = pickups의 길이 = n
• deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
• pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
• 0 ≤ deliveries의 원소 ≤ 50
• 0 ≤ pickups의 원소 ≤ 50
• 트럭의 초기 위치는 물류창고입니다.

입출력 예

cap	n	deliveries	pickups	result
4	5	[1, 0, 3, 1, 2]	[0, 3, 0, 4, 0]	16
2	7	[1, 0, 2, 0, 1, 0, 2]	[0, 2, 0, 1, 0, 2, 0]	30

 

---

문제 해설

 

문제 자체가 길고 설명이 많아서 복잡해보이는것 뿐이지 사실 그렇게 크게 어려운 문제는 아니다.

 

항상 최선의 결과가 나타나려면 갈 수 있는한 가장 최대끝 까지 가서 택배를 전달하는 것이 옳고, 그 끝에서 오면서 가능한 가장 많은 상자를 수거하는것이 옳다.

 

그럼으로, 택배차는 가능한 최대거리 부터 이동한다음 그곳부터 물건을 전달, 물건을 수거 해야한다.

 

그럼으로, 배달마다 언제나 현재 Pickup과 Deliveries배열중 가장 큰 배열사이즈 만큼 이동한 다음, 되돌아와야 할 것 이다.

 

그리고, 가능한 가장 많이 배달해주고, 가능한 가장 많이 챙겨와야 하는 것을 끝부분부터 처리한다.

 

중간중간 다른곳을 방문하던, 최선의 경로를 탐색하던, 이 결과보다 더 좋은 결과가 나올수는 없다.

 

왜냐하면 조건중, 택배차가 출발했을 때, 언제나 택배를 가능한 많이 수거해야하고, 가능한 많이 배송해야하기 때문이다.

 

그리고, 가장 효율적인 거리라는 것은, 이동해야하는 거리가 왕복시 거리의 두배를 넘으면 안된다는 이야기다.

 

이 조건을 지켰을 때를 기준으로 코드를 작성하면, 쉽게 해결할 수 있다.

 

---

첫 번째 시도

#include <string>
#include <vector>
#include <stack>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    stack<int> del;
    stack<int> pic;
    int Maxdel = 0;
    for (auto& def : deliveries) {
        del.push(def);
        Maxdel += def;
    }
    for (auto& def : pickups) 
        pic.push(def);

    while (del.top() == 0)
        del.pop();

    while (pic.top() == 0)
        pic.pop();

    while (pic.size() != 0 && del.size() != 0)
    {
        int Nowcap = min(Maxdel, cap);
        int Move = max(del.size(), pic.size());
        while (Nowcap >= 0 && del.size() > 0) 
        {
            int nowtop = del.top();
            del.top() -= Nowcap;
            Nowcap -= nowtop;
            if (del.top() <= 0) del.pop();
        }
        Nowcap = 0;
        while (Nowcap < cap && pic.size() > 0)
        {
            if (Nowcap + pic.top() <= cap)
            {
                Nowcap += pic.top();
                pic.pop();
            }
            else
            {
                pic.top() -= cap - Nowcap;
                Nowcap = cap;
            }
        }
        answer += Move * 2;
    }

    return answer;
}

실패

 

조건자체를 생각한것과 같이 했으나, 몃가지 오류가 있었다.

 

먼저, 택배를 수거, 배달 하였을 때, 다음배열값이 0일경우 방문하지 않아도되는 곳이기 때문에, 해당위치를 반영해야 한다.

 

그리고, 굳이 덧셈으로 바꿀 필요 없이, 배송과 수거를 같은 while문으로 돌려도 무방하다.

 

초기값 최적화를 위해 가장 끝 값이 0일경우 전부 빼버리게 while문을 작성했는데, 만약 배송할 구간이 없거나 픽업할 구간이 없을경우 터진다.

 

그리고, 언제나 순환할 배열이 존재할 경우 순환해야한다. 첫 While문의 조건항을 &&가 아니라 || 로 바꾸어주어야 한다.

---

두 번째 시도

#include <string>
#include <vector>
#include <stack>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    stack<int> del;
    stack<int> pic;
    int Maxdel = 0;
    int Maxpic = 0;
    for (auto& def : deliveries) {
        del.push(def);
        Maxdel += def;
    }
    for (auto& def : pickups) {
        pic.push(def);
        Maxpic += def;
    }

    while (del.size() > 0 && del.top() == 0)
        del.pop();

    while (pic.size() > 0 && pic.top() == 0)
        pic.pop();

    while (pic.size() != 0 || del.size() != 0)
    {
        int Nowcap = min(Maxdel, cap);
        int Move = max(del.size(), pic.size());
        while (Nowcap >= 0 && del.size() > 0) 
        {
            int nowtop = del.top();
            del.top() -= Nowcap;
            Nowcap -= nowtop;
            if (del.top() <= 0) del.pop();
        }

        Nowcap = min(Maxpic, cap);
        while (Nowcap >= 0 && pic.size() > 0)
        {
            int nowtop = pic.top();
            pic.top() -= Nowcap;
            Nowcap -= nowtop;
            if (pic.top() <= 0) pic.pop();
        }

        answer += Move * 2;
    }

    return answer;
}

성공

 

두개의 조건항을 똑같이 바꾸어주었다. 그리고, 초기값 세팅시 터지지 않도록 수정했다.