[프로그래머스] 택배 배달과 수거하기 (cpp)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/150369?language=cpp

풀이

위 그림에서 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하는 문제이다. N <= 10만이므로 최적해를 찾는 방향으로 생각해야 한다. 잘 생각해보면 맨 끝 (물류창고로부터 가장 먼)에 있는 집부터 차례대로 가능한 최대의 횟수로 배달과 수거를 하는 것이 가장 최적의 선택이며 곧 전체의 최단 거리가 된다.

구현 흐름은 아래와 같다.

1. 배달할 집을 가리키는 인덱스와, 수거할 집을 가리키는 인덱스 두 개를 사용하여 맨 끝 집부터 시작해서 최대한 배달 및 수거를 할 수 있는 집의 위치까지 이동시킨다.
2. 처음 시작했던 두 인덱스 중 더 큰 인덱스까지가 트럭이 왕복한 거리가 되므로 x2를 하여 answer에 더해준다.
3. 두 인덱스가 물류창고로 도달할 때까지 위 과정을 반복한다.

제출할 때 계속 테스트케이스 2번이 실패로 나왔는데, 이유를 찾아보니 맨 끝집이 배달과 수거할 택배의 양이 0일 수도 있다는 사실을 간과했었다. 그래서 처음 두 인덱스를 끝에서부터 0이 아닌 곳을 찾아서 초기값으로 잡아주니 정답이 나왔다.

코드

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

using namespace std;

// n은 10만이므로 그리디로 접근

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    
    int delivery_idx = -1;
    int pickup_idx = -1;
    
    for(int i = n - 1; i >= 0; i--){
        if(deliveries[i] != 0) {
            delivery_idx = i;
            break;
        }
    }
    
    for(int i = n - 1; i >= 0; i--){
        if(pickups[i] != 0) {
            pickup_idx = i;
            break;
        }
    }

    while(1){
        int max_idx = max(delivery_idx, pickup_idx);
        
        if(max_idx == -1) {
            answer = 0;
            break;
        }
        
        answer += (max_idx + 1) * 2;
        
        int delivery_num = cap;
        
        // delivery 배열의 끝에서부터 접근
        for(int i = delivery_idx; i >= 0; i--){
            
            if(deliveries[i] <= delivery_num){
                if(i == 0) delivery_idx = -1;
                delivery_num -= deliveries[i];
            }
            else{ // 현재 배달할 집이 더 많다면
                deliveries[i] -= delivery_num;
                delivery_idx = i;
                break;
            }
        }
        
        // 현재 수거할 수 있는 용량
        int pickup_num = cap;
        
        for(int i = pickup_idx; i >= 0; i--){
            if(pickups[i] <= pickup_num){
                if(i == 0) pickup_idx = -1;
                pickup_num -= pickups[i];
            }
            else{
                pickups[i] -= pickup_num;
                pickup_idx = i;
                break;
            }
        }
        
        if(delivery_idx == -1 && pickup_idx == -1) break;
        
    }
    
    return answer;
}