[Programmers] 택배 배달과 수거하기(Lv.2)

풀이 소요시간 : 90분(60분 초과 : 실패)

문제를 읽어보고 정형적인 풀이법이 떠오르지 않는다면 그리디 알고리즘 문제인 경우가 많은거같다. 이 문제 역시 마찬가지였다. 문제 풀이 방법에 대한 확실한 방법을 찾는데 오래걸렸고, 구현에도 문제가 생겨서 굉장히 오랜 시간이 걸리고 말았다.

접근 방식에 대해 말하자면

deliveries 배열과 pickups 배열의 인덱스를 n-1에서부터 0까지 줄여나가며 둘 중 큰 인덱스 값을 정해 더해주면 되는 문제였다. 어렵게 푼 만큼, 문제 풀이 방식을 꼭 암기하도록 하자.

전체 코드

#include <string>
#include <cmath>
#include <vector>

using namespace std;


long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
  
    
    long long Go = n - 1;
    long long Back = n - 1;
    long long Ans = 0;
    
    while(Go >= 0 || Back >= 0) {
        
        long long Max_Go = 0;
        long long Max_Back = 0;
        long long C = cap;
        
        while(Go >= 0) {
            if(deliveries[Go] > 0 && Max_Go == 0) {
                Max_Go = Go + 1;
            }
            
            if(C - deliveries[Go] >= 0) {
                C -= deliveries[Go];
                Go--;
            } else {
                deliveries[Go] -= C;
                break;
            }          
        }
        
        C = (long long)cap;
        
        
        while(Back >= 0) {
            if(pickups[Back] > 0 && Max_Back == 0) {
                Max_Back = Back + 1;
            }
            
            if(C - pickups[Back] >= 0) {
                C -= pickups[Back];
                Back--;
            } else {
                pickups[Back] -= C;
                break;
            }
        }
        
        Ans += 2 * max(Max_Go, Max_Back);
        
    }
    
    
    return Ans;
}