카카오 2023 Blind Recruitment 택배 배달과 수거하기 c++

#include <string>
#include <vector>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long deli_sum = 0;
    long long pick_sum = 0;
    
    for(auto d : deliveries)
        deli_sum += d;
    
    for(auto p : pickups)
        pick_sum += p;

    long long answer = 0;
    int longest = n-1;
    while(deli_sum > 0 || pick_sum > 0){
        int c1 = cap;
        int dist1 = 0;
        int c2 = cap;
        int dist2 = 0;
        for(int i=longest; i>=0; i--){
            if(deliveries[i] > 0 && c1 > 0) {
                dist1 = i > dist1 ? i : dist1;
                while(c1 > 0 && deliveries[i] > 0) {
                    c1--; deliveries[i]--; deli_sum--;
                }
            }
            if(pickups[i] > 0 && c2 > 0) {
                dist2 = i > dist2 ? i : dist2;
                while(c2 > 0 && pickups[i] > 0) {
                    c2--; pickups[i]--; pick_sum--;
                }
            }
            if(c1==0 && c2==0) break;
        }
        if(deliveries[longest] == 0 && pickups[longest] == 0) longest=max(dist1, dist2);
        answer += max(dist1+1, dist2+1) * 2;
    }
    
    return answer;
}

 

큰 알고리즘은 "가장 먼 집부터 해결"이다.

배달과 수거는 따로 생각하면 된다.

 

간단하게 설명하면 다음과 같다.

1) 트럭이 물류창고를 떠나 다시 오는 것을 한 턴이라고하자.

2) 트럭은 한 턴마다 배달 배열과 수거 배열의 가장 먼 원소부터 cap 만큼을 뺀다.

3) 이 때 max(가장 먼 배달 거리, 가장 먼 수거 거리) * 2가 그 턴에 트럭이 움직인 거리다.

1~3을 모두 배달하고 수거할때까지 반복한다.

 

예를 들어 cap이 5이고 deliveries가  {1, 0, 1, 1, 7, 0}, pickups가 {0, 0, 3, 1, 4, 3} 이라면,

첫 번째 턴에 deliveries는 {1, 0, 1, 1, 2, 0}이 될 것이고, pickups는 {0, 0, 3, 1, 2, 0}이 될 것이다.

이 때, 수거를 위해 6번째 집까지 갔으므로 그 턴에는 6*2=12의 거리를 움직인 것이 된다.

 

1)을 while문을 통해 한 턴 한 턴 돌도록 구현했고,

2)가 while문 안의 메인 로직이다.

3)은 답을 구하는 answer += max(dist1+1, dist2+1) * 2로 표현했다.

위 로직의 반복을 while문의 조건으로 완성시켰다.

 

이 때 매번 for문의 시간 최적화를 위해, 할 일이 남아있는 가장 먼 집을 longest에 저장하여 for문이 돌도록 했다.