[프로그래머스 Level 2] 택배 배달과 수거하기(C++)

코딩테스트 연습 - 택배 배달과 수거하기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

맨 뒤에서부터 deliveries와 pickups의 각각 원소를 0으로 만들어 주면 된다. 가장 중요한 아이디어는 택배 차량 사이즈를 단일로 생각하지 말고 delivery와 pickup을 따로 생각하면 된다. 왜냐하면 지나가는 길에 배송하든 돌아오는 길에 배송하든 상관이 없기 때문이다.

#include <string>
#include <vector>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
	long long answer =0;
	int lastIndex = n - 1;
	for (; lastIndex >= 0; lastIndex--) {
		if (deliveries[lastIndex] != 0 || pickups[lastIndex] != 0) {
			break;
		}
	}
	int remindDel = 0;
	int remindPick = 0;
	for (int i = 0; i <= lastIndex; i++) {
		if (deliveries[i] != 0) {
			remindDel += deliveries[i];
		}
		if (pickups[i] != 0) {
			remindPick += pickups[i];
		}
	}
	while (lastIndex != -1) {
		answer += (lastIndex+1) * 2;
		int del = cap, pick = 0;
		int checked = -1;
		for (; lastIndex>= 0; lastIndex--) {
			if (pick <= cap && pickups[lastIndex] != 0) {
				if (cap - pick >= pickups[lastIndex]) {
					pick += pickups[lastIndex];
					remindPick -= pickups[lastIndex];
					pickups[lastIndex] = 0;
				}
				else {
					pickups[lastIndex] -= (cap - pick);
					remindPick -= (cap-pick);
					if(checked==-1)
						checked = lastIndex;
					pick = cap;
				}
			}
			if (del >= 0 && deliveries[lastIndex] != 0) {
				if (del >= deliveries[lastIndex]) {
					del -= deliveries[lastIndex];
					remindDel -= deliveries[lastIndex];
					deliveries[lastIndex] = 0;
				}
				else {
					deliveries[lastIndex] -= del;
					remindDel -= del;
					if (checked == -1)
						checked = lastIndex;
					del = 0;
				}
			}
			if (del == 0 && pick == cap) {
				break;
			}
			if (pick == cap && remindDel == 0) {
				break;
			}
			if (del == 0 && remindPick == 0) {
				break;
			}
		}
		while (lastIndex != -1 && deliveries[lastIndex] == 0 && pickups[lastIndex] == 0) {
			lastIndex--;
		}
		if (checked != -1) {
			lastIndex = checked;
		}
	}
	return answer;
}