Level 2. 택배 배달과 수거하기

Level 2. 택배 배달과 수거하기

 

 

이동 경로를 최소화하기 위해서는 가장 먼 곳부터 배달과 수거를 마쳐야 한다.

 

배달과 수거를 각각 진행하면서 가장 먼 집을 유지하고, 가장 먼 집까지의 거리를 더하는 방식으로 진행한다.

 

카카오 문제 치고는 파싱이나 다양한 개념들이 섞여있진 않은데, 그렇다고 구현이 마냥 쉽지도 않았다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups)
{
    long long answer = 0;
    int ed = n - (find_if(deliveries.rbegin(), deliveries.rend(), [](int num) { return num != 0; }) - deliveries.rbegin()) - 1;
    int ep = n - (find_if(pickups.rbegin(), pickups.rend(), [](int num) { return num != 0; }) - pickups.rbegin()) - 1;

    while (0 <= ed || 0 <= ep)
    {
        int e = max(ed, ep);
        answer += (1 + e + e + 1);

        int d = cap;

        for (int i = ed; 0 <= i; --i)
        {
            if (deliveries[i] < d)
                d -= deliveries[i],
                deliveries[i] = 0;
            else
                deliveries[i] -= d,
                d = 0;

            ed -= (deliveries[i] == 0);

            if (d < deliveries[i])
                break;
        }

        int p = cap;

        for (int i = ep; 0 <= i; --i)
        {
            if (pickups[i] < p)
                p -= pickups[i],
                pickups[i] = 0;
            else
                pickups[i] -= p,
                p = 0;

            ep -= (pickups[i] == 0);

            if (p < pickups[i])
                break;
        }
    }

    return answer;
}

 

좀 더 간단한 풀이다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups)
{
    long long answer = 0;
    int d = 0, p = 0;

    for (int i = n - 1; 0 <= i; --i)
    {
        if (0 < deliveries[i] || 0 < pickups[i])
        {
            int cnt = 0;

            while (d < deliveries[i] || p < pickups[i])
            {
                ++cnt;
                d += cap;
                p += cap;
            }

            d -= deliveries[i];
            p -= pickups[i];
            answer += (i + 1) * cnt * 2;
        }
    }

    return answer;
}