택배 배달과 수거하기
문제 링크 : 택배 배달과 수거하기
문제 설명
당신은 일렬로 나열된 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 |
| 남은 배달/수거 | 1/0 | 0/3 | 3/0 | 0/4 | 0/0 |
| 남은 배달/수거 | 1/0 | 0/3 | 3/0 | 0/0 | 0/0 |
| 남은 배달/수거 | 0/0 | 0/3 | 0/0 | 0/0 | 0/0 |
| 남은 배달/수거 | 0/0 | 0/0 | 0/0 | 0/0 | 0/0 |
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 |
풀이 방법
- 해당 문제는 언뜻 보면 배달할 택배 상자랑 회수할 택배 상자를 같이 관리해야 할 것으로 보이지만, 실제로는 따로따로 계산을 해서 더 큰 인덱스를 가진 값을 저장하면 된다. 배달 및 수거하는 집을 하나씩 뒤에서부터 순회하면서 용량만큼의 상자를 배달/수거하면 된다.
- 중간에 0이 되는 지점은 그냥 넘어가야 하기 때문에 새로 값을 찾을 때는 0이 아닌 지점을 찾아서 시작했다.
-> 해당 문제 풀이의 시간복잡도는O(N)으로 N은 각 배열의 길이로 최대 100,000이기 때문에 알맞은 알고리즘으로 보인다.
구현
#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 temp_delivery = n - 1, temp_pickup = n - 1;
int delivery = 0, pickup = 0;
while(temp_delivery >= 0 || temp_pickup >= 0){
// 0이 아닌 시작 지점 찾기
while(temp_delivery >= 0 && deliveries[temp_delivery] == 0){
temp_delivery--;
}
while(temp_pickup >= 0 && pickups[temp_pickup] == 0){
temp_pickup--;
}
answer += 2 * max(temp_delivery + 1, temp_pickup + 1);
// 배달/수거할 상자 개수 할당
delivery = cap; pickup = cap;
while(temp_delivery >= 0 && delivery > 0){
if(deliveries[temp_delivery] > delivery){
deliveries[temp_delivery] -= delivery;
delivery = 0;
}else{
delivery -= deliveries[temp_delivery];
deliveries[temp_delivery] = 0;
temp_delivery--;
}
}
while(temp_pickup >= 0 && pickup > 0){
if(pickups[temp_pickup] > pickup){
pickups[temp_pickup] -= pickup;
pickup = 0;
}else{
pickup -= pickups[temp_pickup];
pickups[temp_pickup] = 0;
temp_pickup--;
}
}
}
return answer;
}