택배 배달과 수거하기

https://school.programmers.co.kr/learn/courses/30/lessons/150369

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다.

배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.

배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다.

또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)

트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다.

트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다.

각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때,

트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 

각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

배달 및 수거할 재활용 택배 상자 개수

	집 #1	집 #2	집 #3	집 #4	집 #5
배달	1개	0개	3개	1개	2개
수거	0개	3개	0개	4개	0개

배달 및 수거 과정

	집 #1	집 #2	집 #3	집 #4	집 #5	설명
남은 배달/수거	1/0	0/3	3/0	1/4	2/0	물류창고에서 택배 3개를 트럭에 실어 출발합니다.
남은 배달/수거	1/0	0/3	3/0	0/4	0/0	물류창고에서 5번째 집까지 이동하면서(거리 5) 4번째 집에 택배 1개를 배달하고, 5번째 집에 택배 2개를 배달합니다.
남은 배달/수거	1/0	0/3	3/0	0/0	0/0	5번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 4개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 4개를 트럭에 싣습니다.
남은 배달/수거	0/0	0/3	0/0	0/0	0/0	물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 3개를 배달합니다.
남은 배달/수거	0/0	0/0	0/0	0/0	0/0	3번째 집에서 물류창고까지 이동하면서(거리 3) 2번째 집에서 빈 택배 상자 3개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다.

16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다.

같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만,

이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n,

각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와

각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다.

이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ cap ≤ 50
• 1 ≤ n ≤ 100,000
• deliveries의 길이 = pickups의 길이 = n
  • deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
  • pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
  • 0 ≤ deliveries의 원소 ≤ 50
  • 0 ≤ pickups의 원소 ≤ 50
• 트럭의 초기 위치는 물류창고입니다.

입출력 예

cap	n	deliveries	pickups	result
4	5	[1, 0, 3, 1, 2]	[0, 3, 0, 4, 0]	16
2	7	[1, 0, 2, 0, 1, 0, 2]	[0, 2, 0, 1, 0, 2, 0]	30

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 동일합니다.

입출력 예 #2

배달 및 수거할 재활용 택배 상자 개수

	집 #1	집 #2	집 #3	집 #4	집 #5	집 #6	집 #7
배달	1개	0개	2개	0개	1개	0개	2개
수거	0개	2개	0개	1개	0개	2개	0개

배달 및 수거 과정

	집 #1	집 #2	집 #3	집 #4	집 #5	집 #6	집 #7	설명
남은 배달/수거	1/0	0/2	2/0	0/1	1/0	0/2	2/0	물류창고에서 택배 2개를 트럭에 실어 출발합니다.
남은 배달/수거	1/0	0/2	2/0	0/1	1/0	0/2	0/0	물류창고에서 7번째 집까지 이동하면서(거리 7) 7번째 집에 택배 2개를 배달합니다.
남은 배달/수거	1/0	0/2	2/0	0/1	1/0	0/0	0/0	7번째 집에서 물류창고까지 이동하면서(거리 7) 6번째 집에서 빈 택배 상자 2개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 2개를 트럭에 싣습니다.
남은 배달/수거	1/0	0/2	1/0	0/1	0/0	0/0	0/0	물류창고에서 5번째 집까지 이동하면서(거리 5) 3번째 집에 택배 1개를 배달하고, 5번째 집에 택배 1개를 배달합니다.
남은 배달/수거	1/0	0/1	1/0	0/0	0/0	0/0	0/0	5번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 1개를 수거하고 2번째 집에서 빈 택배 상자 1개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 2개를 트럭에 싣습니다.
남은 배달/수거	0/0	0/1	0/0	0/0	0/0	0/0	0/0	물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 1개를 배달합니다.
남은 배달/수거	0/0	0/0	0/0	0/0	0/0	0/0	0/0	3번째 집에서 물류창고까지 이동하면서(거리 3) 2번째 집에서 빈 택배 상자 1개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다.

30(=7+7+5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다.

같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.

따라서, 30을 return 하면 됩니다.

---

통과된 코드

#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 _delP = -1, _picP = -1;

	for (int i = deliveries.size() - 1; i >= 0; i--)
		if (deliveries[i]) {
			_delP = i;
			break;
		}
	for (int i = pickups.size() - 1; i >= 0; i--)
		if (pickups[i]) {
			_picP = i;
			break;
		}

	while (_delP >= 0 || _picP >= 0) {
		answer += (max(_delP, _picP) + 1) * 2;
		int _del = cap, _pic = cap;
		for (int i = _delP; i >= 0; i--) {
			if (_del >= deliveries[i]) _del -= deliveries[i];
			else {
				deliveries[i] -= _del;
				break;
			}
			_delP--;
		}

		for (int i = _picP; i >= 0; i--) {
			if (_pic >= pickups[i]) _pic -= pickups[i];
			else {
				pickups[i] -= _pic;
				break;
			}
			_picP--;
		}
	}
    
	return answer;
}

더 효율적인 코드

https://school.programmers.co.kr/questions/43364

#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 d = 0;
    int p = 0;
    // 역순으로 벡터를 탐색
    for (int i = n - 1; i >= 0; i--) {
        int cnt = 0; // 왕복 횟수 초기화
        d -= deliveries[i]; // 배달
        p -= pickups[i]; // 픽업 

        // 해당 인덱스를 몇번 반복
        while (d < 0 || p < 0) {
            d += cap;
            p += cap;
            // 해당 위치를 반복하는 횟수를 올려준다
            cnt += 1;
        }
        // (인덱스까지의 거리) * 왕복(2) * 왕복횟수
        answer += (i + 1) * 2 * cnt;
    }

    return answer;
}

출처 : https://school.programmers.co.kr/questions/43364

필자는 생각합니다.

카카오가 코테의 수준을 너무나도 높여버렸습니다.

이젠 레벨2와 레벨3의 구분이라는 것이 있는지 모르겠습니다.

난이도가 다 레벨3이 된 것 같은 기분은 저만 드는 것일까요?

cap만큼의 공간을 사용하여, 배달도 수행하고, 회수도 수행해야 합니다.

이 문제를 풀기위한 당연한 기준들을 한 번 정리해보려고 합니다.

배달할 물건이나, 회수할 물건이 i번째 까지 존재한다면, 당신은 반드시 i번째 까지는 적어도 한 번은 가야합니다.

한 번 출발하여, 물류창고로 돌아오면, cap만큼의 배달을 수행할 수 있고, cap만큼의 물건을 회수 해 올 수 있습니다.

한 곳에서 택배를 전부 배달하지 못했거나, 회수하지 못했다면, 당신은 물류창고로 돌아왔다가, 다시 같은 장소로 떠나야 합니다.

아마, 이 문제들을 심히 고민해보았다면, 3가지의 정의는 내릴 수 있어야 합니다.

그리고 2번 정의에 따라, 물건의 전달이나, 물건의 회수는 항상 최대 cap만큼 수행 할 수 있다는 사실을 알 수 있습니다.

아마, 이해가 되지 않을 수 있습니다. 전달해야 할 물건이 너무 많아서 회수가 불가능한 상황이 생길 수 있지 않느냐고 말이죠.

하지만, 그 문제는 배열을 거꾸로 탐색하면 쉽게 해결 할 수 있습니다.

1번 정의에 따라, 당신은 반드시 전달할 물건이나, 회수할 물건이 있는 장소까지는 도달해야 합니다.

거꾸로 배열을 탐색한다는 의미는, 이미 방문이 가능한 모든 지점들을 왕복했다는 가정하에 문제를 풀게 됩니다.

물류창고에서, 목적지 까지 가는데, 택배가 너무 많아 회수가 불가능 하였다면, 돌아올 때는 이미 모든 장소를 한 번씩 들렸기에,

트럭에 물건이 비어있게 됩니다. 이 때 회수하면 됩니다.

이로써 이런 정의들을 단순화 시켜보자면, 사실 물건을 전달하는 것과, 회수하는 것은 별개로 봐도 상관이 없습니다.

그리고 이 문제는 Greedy한 문제가 됩니다.

트럭이 한 번 떠나게 되면, cap만큼의 물건을 배달할 수 있고, cap만큼의 물건을 회수 할 수 있다는 사실을 이해했다면,

이 문제의 절반을 풀었다고 무방합니다.

이제 배열을 거꾸로 탐색하여, 전달 한 물건이나, 회수 할 물건이 있는지 탐색을 수행합니다.

만약 존재한다면, 해당 값을 어딘가에서 감소 시켜줍니다.

그리고, 전달 할 물건이나 회수 할 물건이 존재하였기에, cap만큼의 배달량, cap만큼의 회수량을 처리 할 수 있다고,

이 값을 증가 시켜줍니다.

만약 한 번 해당 장소에 방문 한 것으로, 커버가 되지 않는다면, 다시 방문하여, cap만큼의 배달량, 회수량을 증가 시켜줍니다.

그 대신에 answer에 추가 할 때는 반복 횟수 만큼 곱해주어야 합니다.

여기서 중요합니다.

cap만큼의 배달량, 회수량을 그대로 사용하여, 다음 값을 계산할 때 그대로 이용합니다.

deliveries[i]가 2, pickups[i]가 3 이고 cap이 3이라고 하면, pickups의 값은 1만큼의 잉여 회수량이 남게 됩니다.

배열을 거꾸로 탐색한다는 의미는, i번째까지 이미 도달하고, 다시 물류창고로 돌아간다는 왕복운동의 기준으로 고려한다는 의미입니다.

이 때 잉여량이 발생하였다면, 어차피 이전 장소에서 한 번 더 사용하면 효율성 높게 업무를 처리 할 수 있게 됩니다.

여기서 주의할 점은, deliveries[i]와 pickups[i]를 가감해도 배달량과 회수량이 남아있다고 하면,

answer에 답을 추가 할 필요가 없습니다. 잉여량이 현재 배달량과 회수량을 커버하므로, 이 경우는 답을 추가하는 실수를 저지르지 맙시다.

설명을 쓰고도 제가 무슨 소리를 하는지 모르는 상황이 되었습니다.

그래도 이 문제를 깊게 고민하였다면, 약간의 도움이 됬으리라고 생각합니다.

감사합니다.

추가 반례

cap	n	deliveries	pickups	result
2	2	[0, 0]	[0, 4]	8
2	2	[0, 0]	[0, 0]	0
2	2	[0, 6]	[0, 0]	12
1	2	[12, 0]	[0, 12]	48
4	4	[25, 24, 51, 0]	[51, 0, 0, 49]	140
5	3	[1, 6, 9]	[5, 10, 20]	34