[1일 1알고] 택배 배달과 수거하기

1. 택배 배달과 수거하기

https://school.programmers.co.kr/learn/courses/30/lessons/150369

프로그래머스

 

택배를 배달해야합니다.

아이디어만 떠올리면 쉽게 해결할 수 있는 문제입니다.

 

cap제한에 따라 택배를 배달할 수 있는데 결국 한번 왕복할 때 cap개의 박스를 배달하고 cap개의 빈박스를 수거할 수 있습니다.

 

그렇다면 한번 왕복할 때 배달하는 집 혹은 수거하는 집들 중 제일 멀리있는 집의 거리를 더해가면 답이 나온다는 것을 알 수 있습니다.

---

#include <string>
#include <vector>

using namespace std;

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

    int didx = n - 1;
    int pidx = n - 1;
    int total = 0;
    for (int i = 0; i < n; ++i)
    {
        total += deliveries[i] + pickups[i];
    }

    while (total > 0)
    {
        int cnt = 0;
        int maxd = 0;
        while (cnt < cap)
        {
            if (didx < 0)
                break;
            if (deliveries[didx] > 0)
            {
                ++cnt;
                --total;
                --deliveries[didx];
                maxd = max(maxd, didx);
            }
            else
            {
                --didx;
            }
        }
        cnt = 0;
        int maxp = 0;
        while (cnt < cap)
        {
            if (pidx < 0)
                break;
            if (pickups[pidx] > 0)
            {
                ++cnt;
                --total;
                --pickups[pidx];
                maxp = max(maxp, pidx);
            }
            else
            {
                --pidx;
            }
        }
        answer += max(maxd+1, maxp+1) * 2;

    }

    return answer;
}

변수 컨트롤이 가장 중요하겠네요