프로그래머스 택배 배달과 수거하기 문제 풀이를 진행하였습니다.
문제 해석
문제를 읽으면 아래와 같은 해석이 가능합니다.
일렬로 나열된 n개의 집에 택배를 배달하며 집에 있는 빈 재활용 택배 상자를 수거하려 합니다.
트럭에는 cap개만큼 상자를 실을 수 있으며, 트럭은 물류창고에서 택배 상자를 실어 배달하고 돌아오면서 택배 상자들을 수거해 물류창고에 내립니다.
각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구해야 합니다.
문제 풀이
문제를 보면 풀기위한 여러 기준들이 보이는데
배달할 물건이나 회수할 물건이 i번째 위치까지 존재한다면, 적어도 한번 이상 i번째까지 움직여 물건를 배달하거나 수거해야 합니다.
i번째까지 배달을 갔으나 한번에 물건을 배달하거나 회수하지 못했을 경우, i번째까지 여러 번 이동하여 물건을 배달하거나 회수해야 합니다.
트럭이 물류창고에서 한번 떠나게 되면 cap만큼 물건을 배달하고 cap만큼 물건을 회수할 수 있으며, 최소거리를 구해야 하기에 제일 멀리 있는 물건들부터 배달하고 회수를 진행을 해주면 됩니다.
이번 문제는 누적합을 사용하여 문제를 풀어주면 됩니다.
맨 뒤에서부서 시작하여 순서대로 집을 확인해 배달해야 하는 물건이나 회수해야 하는 물건이 있는지 확인해줍니다.
만약 둘 중 한가지라도 존재한다면 그 값을 변수에 더해줍니다.
배달할 물건이나 회수할 물건이 i번째 위치에 존재한다면 i번째까지 이동하여 물건을 회수해야 하기 때문에 두 변수값에 cap만큼 빼주며 몇 번 안에 물건을 회수할 수 있는지 확인해줍니다.
이후 물건을 배달하고 회수한 거리를 answer에 저장해줍니다. 물건의 수가 cap보다 많아 여러번 회수하는 경우가 있기 때문에 변수를 추가적으로 생성하여 확인해줍니다.
여기서 두 변수값에 cap을 더하는 이유는 트럭은 한번 이동에 cap만큼 물건을 배달하고 cap만큼 물건을 회수하기 때문입니다.
이런식으로 끝가지 계산해주면 최소거리를 구할 수 있습니다.
전체 코드
제가 처음에 푼 코드보다 더욱 간단하고 빠른 코드가 존재하여 도움을 받았습니다.
https://school.programmers.co.kr/questions/43364
#include <bits/stdc++.h>
#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 deliverySum = 0;
int pickupSum = 0;
for(int i = n-1; i >= 0; i--)
{
int cnt = 0;
deliverySum += deliveries[i];
pickupSum += pickups[i];
while(deliverySum > 0 || pickupSum > 0)
{
deliverySum -= cap;
pickupSum -= cap;
cnt++;
}
answer += (i+1) * 2 * cnt;
}
return answer;
}출저
https://school.programmers.co.kr/learn/courses/30/lessons/150369
