[Programmers] 택배 배달과 수거하기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/150369

프로그래머스

문제에서 주어진 예시를 보면 아래와 같이 그리디하게 접근 가능합니다.

배달/수거를 제일 멀리 있는 집부터 차례대로 진행하며 각 턴마다 제일 멀리 배달한 거리와 제일 멀리 수거한 거리를 비교해 더 높은 값의 두배만큼 이동하면 됩니다. (물류창고 -> cap이 허용되는 만큼 배달 -> cap이 허용되는만큼 수거 -> 물류창고)

여기서 두배로 이동하는 이유는 물류창고로부터 배달 혹은 수거하는 집까지 왕복을 해야하기 때문입니다. 

 

	#include <string>
	#include <vector>
	#include <algorithm>
	using namespace std;
	vector<int> getFarthestForEachTurn(vector<int> &v, int cap)
	{
	vector<int> farthest;
	int capacity = cap;
	int farthestIdx = -1;
	for (int i = v.size() - 1; i >= 0; )
	{
	if (v[i] == 0)
	{
	i--;
	continue;
	}
	int diff = min(capacity, v[i]);
	capacity -= diff;
	v[i] -= diff;
	farthestIdx = (farthestIdx == -1 ? i : farthestIdx);
	if (capacity == 0)
	{
	farthest.push_back(farthestIdx + 1);
	capacity = cap;
	farthestIdx = -1;
	}
	}
	if (farthestIdx != -1)
	{
	farthest.push_back(farthestIdx + 1);
	}
	return farthest;
	}
	long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups)
	{
	long long answer = 0;
	vector<int> deliveriesFarthest = getFarthestForEachTurn(deliveries, cap);
	vector<int> pickupsFarthest = getFarthestForEachTurn(pickups, cap);
	for (int i = 0, j = 0; i < deliveriesFarthest.size() || j < pickupsFarthest.size(); i++, j++)
	{
	int deliveryMaxLen = i < deliveriesFarthest.size()
	? deliveriesFarthest[i] : 0;
	int pickupMaxLen = j < pickupsFarthest.size()
	? pickupsFarthest[j] : 0;
	answer += max(deliveryMaxLen, pickupMaxLen) * 2;
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub

 

 

개발환경: Programmers IDE

지적, 조언, 질문 환영합니다! 질문 남겨주세요~