풀이 소요시간 : 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;
}