❓문제 설명

문제 요약

• n개의 집에 택배를 배달하려고한다. 배달을 하면서 빈 재활용 택배 상자들은 수거해온다.
• 집과 집 사이의 거리는 모두 1이다.
• 트럭에는 cap개의 택배 상자를 실을 수 있다. 물류창고(시작 위치)에서 택배를 실어서 배달한 뒤 돌아오면서 최대 cap개 만큼 수거해올 수 있다.
• 이때, 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구한다.

이 예시는 cap이 4 일 때 최소 이동 거리 입니다.

택배 3개를 트럭에 실어서 집 #5까지 이동하면서 집 #4와 집 #5에 3개의 택배를 배달합니다. 이때, 집 #5까지 거리 5만큼 이동했습니다.

다음으로 다시 물류창고로 이동하면서 집 #4에 있는 4개의 빈 택배를 수거해갑니다. cap이 4이므로 최대 4개까지 실을 수 있습니다. 이때, 집 #5에서 물류창고까지 거리 5만큼 이동했습니다.

물류창고에서 택배 4개를 실어서 집 #3까지 이동하면서 집 #1과 집 #3에 4개의 택배를 배달합니다. 이때, 집 #3까지 거리 3만큼 이동했습니다.

집 #3에서 물류창고까지 돌아가면서 집 #2에 있는 빈 택배 3개를 수거해갑니다. 이때, 집 #3에서 물류창고까지 거리 3만큼 이동했습니다.

모든 택배를 배달하고 수거했을 때 총 이동 거리는 (5 + 5 + 3 + 3) = 16이 됩니다.

🎯문제 해결 방법

이 문제는 그리디하게 풀 수 있습니다.

문제에서 알 수 있는 점으로는 집 #3까지 이동하면서 3개의 택배를 배달했으면 돌아갈 때 3개의 택배를 수거할 수 있는 공간이 생기게됩니다.

cap 만큼의 택배를 실어서 갔는데도 다 못 실었다면 한 번더 이동해야합니다. cap이 4일 때 집 #5에 배달해야하는 택배가 5개라면 무조건 집 #5까지 2번은 와야합니다. 그래서 가장 뒤에 집부터 해결해야합니다.

	for(int i=n-1; i>=0; i--) {
        a -= d[i];
        b -= p[i];
        int cnt = 0;
        while(a < 0 || b < 0) {
            a += cap;
            b += cap;
            cnt++;
        }
        ans += (i + 1) * 2 * cnt;
    }

a는 배달해야하는 택배 수, b는 수거해야하는 택배 수 입니다.

뒤에서 부터 해당 집에 배달해야하는 택배 수는 a에서 빼주고 수거해야하는 택배 수는 b에서 빼줍니다.

while문을 통해서 a와 b 둘 모두 양수가 될 때까지(배달과 수거를 모두 했다) cap 만큼 더해주고 cnt를 하나씩 더해줍니다.

마지막으로 ans에 왕복 * 이동 횟수(cnt) 의 값을 더해줍니다.

💻전체 코드

#include <string>
#include <vector>
using namespace std;
typedef long long ll;

ll solution(int cap, int n, vector<int> d, vector<int> p) {
    ll ans = 0;
    ll a = 0;
    ll b = 0;
    for(int i=n-1; i>=0; i--) {
        a -= d[i];
        b -= p[i];
        int cnt = 0;
        while(a < 0 || b < 0) {
            a += cap;
            b += cap;
            cnt++;
        }
        ans += (i + 1) * 2 * cnt;
    }
    return ans;
}