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

프로그래머스

 

📄 문제

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

 

📝 풀이

#include <string>
#include <vector>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
	int d = n - 1, p = n - 1;

    // 최초 1회 가장 먼저 배달, 픽업해야 하는 거리 획득
	while (d >= 0 && deliveries[d] == 0)
		--d;

	while (p >= 0 && pickups[p] == 0)
		--p;

	long long answer = 0;
	while (d >= 0 || p >= 0)
	{
        // 배달 또는 픽업해야 하는 개수
		int deliver = cap;
		int pickup = cap;

        // 가야하는 거리
		int target = max(d, p);

        // 배달을 하는 경우
		while (d >= 0 && deliver > 0)
		{
			int land = min(deliver, deliveries[d]);
			deliveries[d] -= land;
			deliver -= land;

			while (d >= 0 && deliveries[d] == 0)
				--d;
		}

        // 픽업을 하는 경우
		while (p >= 0 && pickup > 0)
		{
			int pick = min(pickup, pickups[p]);
			pickups[p] -= pick;
			pickup -= pick;

			while (p >= 0 && pickups[p] == 0)
				--p;
		}

        // 거리의 2배만큼 더하기
		answer += ((target + 1) * 2);
	}

	return answer;
}

• 구현 방식의 문제로 특정 알고리즘을 사용하기보다 문제를 이해하고 해결해야하는것이 더욱 컸던 문제였습니다.

 

solution(2, 2, { 0,0 }, { 0, 0 });
solution(2, 2, { 0,6 }, { 1, 6 });
solution(1, 4, { 1, 1, 1, 2 }, { 1, 1, 1, 2 });
solution(4, 5, { 1, 0, 3, 1, 2 }, { 0, 3, 0, 4, 0 });
solution(2, 7, { 1, 0, 2, 0, 1, 0, 2 }, { 0, 2, 0, 1, 0, 2, 0 });

• 이 테스트 케이스를 모두 만족하여 문제를 해결하였습니다.