9. 택배 배달과 수거하기

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

일단 그리디하게 접근해보면 끝에 있는 지점에서 각각 d[idx], p[idx]의 개수를 (d, p) 라고 하면 이 개수가 (cap, cap) 개 이하가 될 때까지 채울 수 있다는 것을 알 수 있었다.

여기서 내가 한 실수는 (d, p) 를 채우는 과정을 같이 진행했다는 점인데 문제는 이렇게 되면 d와 p를 따로 볼 때보다 반복을 더 진행하게 된다는 점이다.
만약 (0, 0) 지점이 중간에 존재한다면 d 또는 p 둘 중 하나는 이미 지나친 지점인데 앞에서 값을 제거하면서 재방문을 하게 되고 이것을 따로따로 계산하게 되면 최적화가 될 것이다.

시간복잡도는 최악의 경우 1개씩 제거할 때 모든 원소가 50이며, 10^5 만큼 있는 상태이므로 50 x 10^5 x 2 == 10^7 정도가 될 것이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll solution(int cap, int n, vector<int> d, vector<int> p) 
{
    ll ans = 0;
    ll didx = n - 1, pidx = n - 1;
    while (didx >= 0 && d[didx] == 0) didx--;
    while (pidx >= 0 && p[pidx] == 0) pidx--;
    
    while (didx >= 0 || pidx >= 0)
    {   
        ans += (max(didx, pidx) + 1) * 2;
        ll a = 0, b = 0;
        
        while (didx >= 0)
        {
            int ra = cap - a;
            int ma = min(d[didx], ra);
            a += ma, d[didx] -= ma;
            if (d[didx] == 0) didx--;
            else break;
        }
        
        while (pidx >= 0)
        {
            int rb = cap - b;
            int mb = min(p[pidx], rb);
            b += mb, p[pidx] -= mb;
            if (p[pidx] == 0) pidx--;
            else break;
        }
    }
    
    return ans;
}